Decentralized sketching of low-rank matrices

We address a low-rank matrix recovery problem where each column of a rank-r matrix X ? R^d1×^d2 is compressed beyond the point of individual recovery to R^L with L « d₁. Leveraging the joint structure among the columns, we propose a method to recover the matrix to within an e relative error in the Frobenius norm from a total of O(r(d₁ + d₂) log⁶(d₁ + d₂)/e²) 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.