TY - JOUR
T1 - Decentralized sketching of low-rank matrices
AU - Srinivasa, Rakshith S.
AU - Lee, Kiryung
AU - Junge, Marius
AU - Romberg, Justin
N1 - Funding Information:
∗This work was supported in part NSF CCF-1718771, NSF DMS 18-00872 and in part by C-BRIC, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA.
Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
PY - 2019
Y1 - 2019
N2 - We address a low-rank matrix recovery problem where each column of a rank-r matrix X ? Rd1×d2 is compressed beyond the point of individual recovery to RL with L « d1. 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(d1 + d2) log6(d1 + d2)/e2) 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 `2-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.
AB - We address a low-rank matrix recovery problem where each column of a rank-r matrix X ? Rd1×d2 is compressed beyond the point of individual recovery to RL with L « d1. 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(d1 + d2) log6(d1 + d2)/e2) 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 `2-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.
UR - http://www.scopus.com/inward/record.url?scp=85090174119&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090174119&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85090174119
SN - 1049-5258
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -