Abstract

We address a low-rank matrix recovery problem where each column of a rank-r matrix is compressed beyond the point of individual recovery to with Leveraging the joint structure among the columns, we propose a method to recover the matrix to within an  relative error in the Frobenius norm from a total of observations. This guarantee holds uniformly for all incoherent matrices of rank r. In our method, we propose to use a novel matrix norm called the mixed-norm along with the maximum -norm of the columns to design a new convex relaxation for low-rank recovery that is tailored to our observation model. We also show that the proposed mixed-norm, the standard nuclear norm, and the max-norm are particular instances of convex regularization of low-rankness via tensor norms. Finally, we provide a scalable ADMM algorithm for the mixed-norm-based method and demonstrate its empirical performance via large-scale simulations.