Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation
Authors: Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
Organizations: Simons Institute for the Theory of Computing, UC Berkeley · University of Illinois, Chicago · Rice University · Massachusetts Institute of Technology
Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M∈Rn×n, a non-negative weight matrix W∈R≥0n×n, a parameter k, the goal is to output two matrices X,Y∈Rn×k such that ∥W∘(M−XY⊤)∥F is minimized, where ∘ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the cost of each iteration of [LLR16] from ∥W∥0k2 to ∥W∥0k where ∥W∥0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. We also replace the random initialization of [LLR16], whose claimed guarantee fails, by subspace iteration from a Gaussian start, so our total running time of O((∥W∥0k+nk3)log(1/ε)) includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance γn of the all-ones matrix for a γ that is polynomially small in n.
Figures & tables
Notation
Meaning
X
Matrix for exact regression solve
X
Clipped matrix of X
X
QR factor of X=XR
X
Matrix for approximate regression solve
X
Clipped matrix of X
Table 1: Summarization of notations regarding exact and approximate regression solves. By “clipped”, we mean zeroing out rows with large ℓ2 norms.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Notation
Meaning
X
Optimal matrix for exact regression
X
Clipped matrix of X
X
Optimal matrix for sketched regression
X
Clipped matrix of X
Appendix
Table 2: For convenience, we provide a table to summarize the notations in Lemma D.9 .
References
Init
Time
[ 48 ]
Random †
O((∥W∥0k2+nk3)log(1/ϵ))
[ 48 ]
SVD
O(n3)+O((∥W∥0k2+nk3)log(1/ϵ))
Theorem G.7
SVD
O(n3)+O((∥W∥0k+nk3)log(1/ϵ))
Theorem 4.6
Fast SVD (Algorithm 5 )
O((∥W∥0k+nk3)log(1/ϵ))
Appendix
Table 3: Summary of results. Every row states the error bound O(α−1kτ)∥W∘N∥+ϵ . † The random-initialization guarantee of [ 48 ] fails on the example of Remark H.6 .
Distribution
Time of the exact solver
Time of the approximate solver
% speedup
Exact solver error
Approximate solver error
Laplace
234
205
12.39%
1.54×10−4
3.56×10−3
Gaussian
247
216
12.55%
3.85×10−4
1.33×10−3
Uniform
248
207
16.53%
1.34×10−5
4.99×10−4
Appendix
Table 4: Experimental results of Algorithm 1 for the matrix completion problem.
Distribution
Time of the exact solver
Time of the approximate solver
% speedup
Exact solver error
Approximate solver error
Laplace
249
222
10.84%
2.11×10−4
4.71×10−4
Gaussian
223
204
8.52%
6.29×10−5
2.15×10−4
Uniform
221
215
2.71%
3.00×10−5
7.13×10−5
Appendix
Table 5: Experimental results of Algorithm 1 for the weighted low-rank approximation.