TY - GEN
T1 - Scalable algorithms for locally low-rank matrix modeling
AU - Gu, Qilong
AU - Trzasko, Joshua D.
AU - Banerjee, Arindam
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/12/15
Y1 - 2017/12/15
N2 - We consider the problem of modeling data matrices with locally low rank (LLR) structure, a generalization of the popular low rank structure widely used in a variety of real world application domains ranging from medical imaging to recommendation systems. While LLR modeling has been found to be promising in real world application domains, limited progress has been made on the design of scalable algorithms for such structures. In this paper, we consider a convex relaxation of LLR structure, and propose an efficient algorithm based on dual projected gradient descent (D-PGD) for computing the proximal operator. While the original problem is non-smooth, so that primal (sub)gradient algorithms will be slow, we show that the proposed D-PGD algorithm has geometrical convergence rate. We present several practical ways to further speed up the computations, including acceleration and approximate SVD computations. With experiments on both synthetic and real data from MRI (magnetic resonance imaging) denoising, we illustrate the superior performance of the proposed D-PGD algorithm compared to several baselines.
AB - We consider the problem of modeling data matrices with locally low rank (LLR) structure, a generalization of the popular low rank structure widely used in a variety of real world application domains ranging from medical imaging to recommendation systems. While LLR modeling has been found to be promising in real world application domains, limited progress has been made on the design of scalable algorithms for such structures. In this paper, we consider a convex relaxation of LLR structure, and propose an efficient algorithm based on dual projected gradient descent (D-PGD) for computing the proximal operator. While the original problem is non-smooth, so that primal (sub)gradient algorithms will be slow, we show that the proposed D-PGD algorithm has geometrical convergence rate. We present several practical ways to further speed up the computations, including acceleration and approximate SVD computations. With experiments on both synthetic and real data from MRI (magnetic resonance imaging) denoising, we illustrate the superior performance of the proposed D-PGD algorithm compared to several baselines.
UR - http://www.scopus.com/inward/record.url?scp=85043986246&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043986246&partnerID=8YFLogxK
U2 - 10.1109/ICDM.2017.23
DO - 10.1109/ICDM.2017.23
M3 - Conference contribution
AN - SCOPUS:85043986246
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 137
EP - 146
BT - Proceedings - 17th IEEE International Conference on Data Mining, ICDM 2017
A2 - Karypis, George
A2 - Alu, Srinivas
A2 - Raghavan, Vijay
A2 - Wu, Xindong
A2 - Miele, Lucio
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 17th IEEE International Conference on Data Mining, ICDM 2017
Y2 - 18 November 2017 through 21 November 2017
ER -