Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex Optimization
This addresses scalability issues in low-rank matrix estimation for applications like signal processing or machine learning, offering a more efficient convex method with better sample complexity, though it is incremental in improving upon prior nonconvex approaches.
The paper tackles the problem of recovering low-rank matrices from rank-one projections by proposing an unlifted convex optimization estimator that operates in a lower-dimensional space, achieving exact recovery with high probability when the number of measurements exceeds r^2(d1+d2) up to logarithmic factors, which improves on existing nonconvex iterative algorithms.
We study an estimator with a convex formulation for recovery of low-rank matrices from rank-one projections. Using initial estimates of the factors of the target $d_1\times d_2$ matrix of rank-$r$, the estimator admits a practical subgradient method operating in a space of dimension $r(d_1+d_2)$. This property makes the estimator significantly more scalable than the convex estimators based on lifting and semidefinite programming. Furthermore, we present a streamlined analysis for exact recovery under the real Gaussian measurement model, as well as the partially derandomized measurement model by using the spherical $t$-design. We show that under both models the estimator succeeds, with high probability, if the number of measurements exceeds $r^2 (d_1+d_2)$ up to some logarithmic factors. This sample complexity improves on the existing results for nonconvex iterative algorithms.