Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex Optimization

DOI10.1137/20M1330099MaRDI QIDQ6338173arXivFDO

Authors Sohail Bahmani, Kiryung Lee

Publication date 6 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.1137/20M1330099

Mathematics Subject Classification ID

Convex programming (90C25) Estimation in multivariate analysis (62H12) Matrix completion problems (15A83) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

arXiv classification

cs.LGmath.STstat.MLstat.TH

Abstract: 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}imes{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.

This page was built for publication: Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338173)