Cone-constrained Principal Component Analysis
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 v 0 . The unknown vector is constrained to belong to a cone C v 0 . 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.
The authors consider the model of noisy quadratic measurements (rank1 matrix plus noise), where we want to estimate the spike that generates the rank-1 matrix. They refer to this model as a quadratic observation model.Similar estimation problems that come with non-convex constraints (i.e., sparse PCA) have been analyzed where there is a gap between minimax risk and tractable estimators. Here the authors  consider convex cone constraints, (which don't render the problem any easier at first sight). Although the ML-optimization problem is computationally intractable, in the general case, they can show that a projected version of the power method is almost optimal in terms of minimax risk estimation, and approximates the ML performance within a constant gap. In the case of the nonnegative cone, they show that their analysis can be tightened to an almost zero gap between the ML and the projected power method.In summary, their contribution is three fold: - they present the information theoretic bounds for the estimation problem- they present the risk of the ML estimator using the gaussian dimension of the involved cone- they use a projected power method algorithm to essentially achieve ML performance.I generally really liked the paper; it’s an original and significant contribution to the relevant literature. I think that the use of the gaussian dimension of the cone for quadratic measurement problems seems new and very promising. The authors bound the minimax rate using that precisely. I wonder if there is any relevance to the recent phase recovery problem.Similarity with concurrent works of [1] and [2]:Some of the results look very similar to some recent works [1] and [2], where information theoretic bounds and a similar approximate message passing/ projected power method was used. It seems that section 5 establishes the same result as the work of [1]. However, the submission date of [1] is later than the present manuscript was submitted, and the works can be considered concurrent.The presented work here however is much more general and very significant to the relevant literature; the above comment is only made due to the relevance between the results.Some typos:typo in line 137, reference is missingequation (3), subjectto -> subject to[1] “Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics”Andrea Montanari, Emile Richardhttp://arxiv.org/pdf/1406.4775v1.pdf[2] “Information-theoretically Optimal Sparse PCA”Yash Deshpande, Andrea Montanarihttp://arxiv.org/pdf/1402.2238v2.pdf