Cone-constrained Principal Component Analysis

 

From the paper:

 

However we identify a large class of constraints for which estimation appears to be tractable, despite the corresponding maximum likelihood problem is non-convex. This shows that computational tractability is not immediately related to simple considerations of convexity or worst-case complexity.

 ah ! here it is: Cone-constrained Principal Component Analysis by Yash Deshpande, Andrea Montanari, Emile Richard

Estimating a vector from noisy quadratic observations is a task that arises naturally in many contexts, from dimensionality reduction, to synchronization and phase retrieval problems. It is often the case that additional information is available about the unknown vector (for instance, sparsity, sign or magnitude of its entries). Many authors propose non-convex quadratic optimization problems that aim at exploiting optimally this information. However, solving these problems is typically NP-hard. We consider a simple model for noisy quadratic observation of an unknown vector v0. The unknown vector is constrained to belong to a cone C 3v0. While optimal estimation appears to be intractable for the general problems in this class, we provide evidence that it is tractable when C is a convex cone with an efficient projection. This is surprising, since the corresponding optimization problem is non-convex and –from a worst case perspective– often NP hard. We characterize the resulting minimax risk in terms of the statistical dimension of the cone (C).This quantity is already known to control the risk of estimation from gaussian observations and random linear measurements. It is rather surprising that the same quantity plays a role in the estimation risk from quadratic measurements.

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.