Matrix Approximation under Local Low-Rank Assumption
Authors: Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer
ICLR 2013

Abstract: Matrix approximation is a common tool in machine learning for building accurate prediction models for recommendation systems, text mining, and computer vision. A prevalent assumption in constructing matrix approximations is that the partially observed matrix is of low-rank. We propose a new matrix approximation model where we assume instead that the matrix is only locally of low-rank, leading to a representation of the observed matrix as a weighted sum of low-rank matrices. We analyze the accuracy of the proposed local low-rank modeling. Our experiments show improvements in prediction accuracy in recommendation tasks.

Matrix Approximation
under Local Low-Rank Assumption
Joonseok Leea, Seungyeon Kima, Guy Lebanona, b, Yoram Singerb
a College of Computing, Georgia Institute of Technology, Atlanta, GA 30332
b Google Research, Mountain View, CA 94043
{jlee716@, seungyeon.kim@, lebanon@cc.}gatech.edu, singer@google.com
Abstract
Matrix approximation is a common tool in machine learning for building accurate
prediction models for recommendation systems, text mining, and computer vision.
A prevalent assumption in constructing matrix approximations is that the partially
observed matrix is of low-rank. We propose a new matrix approximation model
where we assume instead that the matrix is only locally of low-rank, leading to a
representation of the observed matrix as a weighted sum of low-rank matrices. We
analyze the accuracy of the proposed local low-rank modeling. Our experiments
show improvements of prediction accuracy in recommendation tasks.
1 Introduction
Matrix approximation is a common task in machine learning. Given a few observed matrix entries
{Ma1,b1 ,...,M am,bm}, matrix approximation constructs a matrix ˆM that approximates M at its
unobserved entries. In general, the problem of completing a matrix M based on a few observed
entries is ill-posed, as there are an inﬁnite number of matrices that perfectly agree with the observed
entries of M. Thus, we need additional assumptions such that M is a low-rank matrix. More
formally, we approximate a matrixM ∈Rn1×n2 by a rank-rmatrix ˆM = UV T , where U ∈Rn1×r,
V ∈Rn2×r, and r≪min(n1,n2). In this note, we assume that M behaves as a low-rank matrix in
the vicinity of certain row-column combinations, instead of assuming that the entire M is low-rank.
We therefore construct several low-rank approximations of M, each being accurate in a particular
region of the matrix. Smoothing the local low-rank approximations, we express ˆM as a linear
combination of low-rank matrices that approximate the unobserved matrix M. This mirrors the
theory of non-parametric kernel smoothing, which is primarily developed for continuous spaces,
and generalizes well-known compressed sensing results to our setting.
2 Global and Local Low-Rank Matrix Approximation
We describe in this section two standard approaches for low-rank matrix approximation (LRMA).
The original (partially observed) matrix is denoted byM ∈Rn1×n2 , and its low-rank approximation
by ˆM = UV T , where U ∈Rn1×r, V ∈Rn2×r, r≪min(n1,n2).
Global LRMA Incomplete SVD is a popular approach for constructing a low-rank approximation
ˆM by minimizing the Frobenius norm over the set A of observed entries of M:
(U,V ) = arg min
U,V
∑
(a,b)∈A
([UV T ]a,b −Ma,b)2. (1)
Another popular approach is minimizing the nuclear norm of a matrix (deﬁned as the sum of singular
values of the matrix) satisfying constraints constructed from the training set:
ˆM = arg min
X
∥X∥∗, s.t. ∥ΠA(X−M)∥F <α (2)
1
arXiv:1301.3192v1  [cs.LG]  15 Jan 2013
M
s
u
T ( u )R
n 1 ⇥ n 2
T
(s)
Ms Mt
M
T(u)
Tt(t)
T(t) Tu(t)=Tu(u)+✏=Mu+✏
Tu(u)
Mu
Tu(t)
Tt(u)
Figure 1: For illustrative purposes, we assume a distance function dwhose neighborhood structure
coincides with the natural order on indices. That is, s = (a,b) is similar to u = (a′,b′) if |a−a′|
and |b−b′|are small. (Left) For all s ∈[n1] ×[n2], the neighborhood {s′ : d(s,s′) < h}in
the original matrix M is approximately described by the corresponding entries of the low-rank
matrix T(s) (shaded regions of M are matched by lines to the corresponding regions in T(s) that
approximate them). If d(s,u) is small, T(s) is similar to T(u), as shown by their spatial closeness
in the embedding space Rn1×n2 . (Right) The original matrix M (bottom) is described locally by the
low-rank matrices T(t) (near t) and T(u) (near u). The lines connecting the three matrices identify
identical entries: Mt = Tt(t) and Mu = Tu(u). The equation at the top right shows a relation
tying the three patterned entries. Assuming the distance d(t,u) is small, ϵ = Tu(t) −Tu(u) =
Tu(t) −Mu(u) is small as well.
where ΠA : Rn1×n2 →Rn1×n2 is the projection deﬁned by [ΠA(M)]a,b = Ma,b if (a,b) ∈A and 0
otherwise, and ∥·∥F is the Frobenius norm.
Minimizing the nuclear norm ∥X∥∗is an effective surrogate for minimizing the rank of X. One
advantage of (2) over (1) is that we do not need to constrain the rank of ˆM in advance. However,
problem (1) is substantially easier to solve than problem (2).
Local LRMA In order to facilitate a local low-rank matrix approximation, we need to pose an
assumption that there exists a metric structure over [n1] ×[n2], where [n] denotes the set of integers
{1,...,n }. Formally, d((a,b),(a′,b′)) reﬂects the similarity between the rowsaand a′and columns
band b′. In the global matrix factorization setting above, we assume that the matrix M ∈Rn1×n2
has a low-rank structure. In the local setting, however, we assume that the model is characterized by
multiple low-rank n1 ×n2 matrices. Speciﬁcally, we assume a mapping T : [n1] ×[n2] →Rn1×n2
that associates with each row-column combination [n1] ×[n2] a low rank matrix that describes
the entries of M in its neighborhood (in particular this applies to the observed entries A): T :
[n1] ×[n2] →Rn1×n2 where Ta,b(a,b) = Ma,b. Note that in contrast to the global estimate in
Global LRMA, our model now consists of multiple low-rank matrices, each describing the original
matrix M in a particular neighborhood. Figure 1 illustrates this model.
Without additional assumptions, it is impossible to estimate the mappingTfrom a set of m<n 1n2
observations. Our additional assumption is that the mapping T is slowly varying. Since the domain
of T is discrete, we assume that T is H ¨older continuous. Following common approaches in non-
parametric statistics, we deﬁne a smoothing kernel Kh(s1,s2), where s1,s2 ∈[n1] ×[n2], as a
non-negative symmetric unimodal function that is parameterized by a bandwidth parameter h >0.
A large value of himplies that Kh(s,·) has a wide spread, while a small hcorresponds to narrow
spread of Kh(s,·). We use, for example, the Epanechnikov kernel, deﬁned as Kh(s1,s2) = 3
4 (1 −
d(s1,s2)2)1{d(s1,s2)<h}. We denote by K(a,b)
h the matrix whose (i,j)-entry is Kh((a,b),(i,j)).
Incomplete SVD (1) and compressed sensing (2) can be extended to local version as follows
Incomplete SVD: ˆT(a,b) = arg min
X
∥K(a,b)
h ⊙ΠA(X−M)∥F s.t. rank (X) = r (3)
Compressed Sensing: ˆT(a,b) = arg min
X
∥X∥∗ s.t. ∥K(a,b)
h ⊙ΠA(X−M)∥F <α, (4)
2
5 10 15 20 25 30 35 40 450.78
0.79
0.8
0.81
0.82
0.83
0.84
MovieLens 10M
Number of Anchor Points
RMSE
 
 
Global(r=5)
Global(r=7)
Global(r=10)
Global(r=15)
Local(r=5)
Local(r=7)
Local(r=10)
Local(r=15)
DFC
5 10 15 20 25 30 35 40 45
0.83
0.84
0.85
0.86
0.87
0.88
0.89
0.9
Netflix
Number of Anchor Points
RMSE
 
 
Global(r=5)
Global(r=7)
Global(r=10)
Global(r=15)
Local(r=5)
Local(r=7)
Local(r=10)
Local(r=15)
DFC
Netflix Winner
Figure 2: RMSE of global-LRMA, local-LRMA, and other baselines on MovieLens 10M (Left) and
Netﬂix (Right) dataset. Local-LRMA models are indicated by thick solid lines, while global-LRMA
models are indicated by dotted lines. Models with same rank are colored identically.
where ⊙denotes a component-wise product of two matrices, [A⊙B]i,j = Ai,jBi,j.
The two optimization problems above describe how to estimate ˆT(a,b) for a particular choice of
(a,b) ∈[n1] ×[n2]. Conceptually, this technique can be applied for each test entry (a,b), result-
ing in the matrix approximation ˆMa,b = ˆTa,b(a,b), where (a,b) ∈ [n1] ×[n2]. However, this
requires solving a non-linear optimization problem for each test index (a,b) and is thus computa-
tionally prohibitive. Instead, we use Nadaraya-Watson local regression with a set ofqlocal estimates
ˆT(s1),..., ˆT(sq), in order to obtain a computationally efﬁcient estimateˆˆT(s) for all s∈[n1]×[n2]:
ˆˆT(s) =
q∑
i=1
Kh(si,s)∑q
j=1 Kh(sj,s)
ˆT(si) . (5)
Equation (5) is simply a weighted average ofˆT(s1),..., ˆT(sq), where the weights ensure that values
of ˆT at indices close to scontribute more than indices further away from s.
Note that the local version can be faster than global SVD since (a) each low-rank approximation is
independent of each other, so can be computed in parallel, and (b) the rank used in the local SVD
model can be signiﬁcantly lower than the rank used in a global one. If the kernel Kh has limited
support (Kh(s,s′) is often zero), the regularized SVD problems would be sparser than the global
SVD problem, resulting in additional speedup.
3 Experiments
We compare local-LRMA to global-LRMA and other state-of-the-art techniques on popular recom-
mendation systems datasets: MovieLens 10M and Netﬂix. We split the data into 9:1 ratio of train
and test set. A default prediction value of 3.0 was used whenever we encounter a test user or item
without training observations. We use the Epanechnikov kernel with h1 = h2 = 0.8, assuming a
product form Kh((a,b),(c,d)) = K′
h1 (a,c)K′′
h2 (b,d). For distance function d, we use arccos dis-
tance, deﬁned as d(x,y) = arccos (⟨x,y⟩/∥x∥∥y∥). Anchor points were chosen randomly among
observed training entries. L2 regularization is used for local low-rank approximation.
Figure 2 graphs the RMSE of Local-LRMA and global-LRMA as well as the recently proposed
method called DFC (Divide-and-Conquer Matrix Factorization) as a function of the number of an-
chor points. Both local-LRMA and global-LRMA improve as r increases, but local-LRMA with
rank r ≥5 outperforms global-LRMA with any rank. Moreover, local-LRMA outperforms global-
LRMA in average with even a few anchor points (though the performance of local-LRMA improves
further as the number of anchor points qincreases).
3


Peer review:
[Review]:
Matrix Approximation under Local Low-Rank Assumption

Paper summary

This paper deals with low-rank matrix approximation/completion. To reconstruct a matrix element M_{i,j}, the proposed method performs a weighted low rank matrix approximation which considers a similarity metric between matrix coordinates. More precisely, the weighting scheme emphasizes reconstruction errors close to the element {i,j} to reconstruct. As a computational speedup, the authors perform the low rank approximation only on a small set of coordinates and approximate the reconstruction for any coordinate through kernel estimation.

Review Summary

The core idea of the paper is interesting and could be helpful in many practical applications of low rank decomposition. The paper reads well and is technically correct. On the negative side, I feel that the availability of a meaningful similarity metric between coordinates should be discussed. The experimental section could be greatly improved. There is no reference to related work at all.

Review 

In many application of matrix completion, the low rank decomposition algorithm is here to circumvent the fact that no meaningful similarity metric between coordinate pairs is available. For instance, if such a metric is available in a collaborative filtering scenario, one would simply take the input (customer, item) fetch its neighbors and average its ratings. Your algorithm presuppose the availability of such a metric, could you discuss this core aspect of your proposal in the paper?

Following on this idea, would you consider as baseline performing the Nadaraya-Watson kernel regression on the matrix itself and reports the result in your experimental section. This would be meaningful to quantify how much comes from the low rank smoothing and how much comes simply from the quality of the similarity metric.

Still in the experimental section, 
- would you consider validating the kernel width?
- discuss the influence of the L2 regularizer which is not even introduced in the previous sections
- define clearly the d you use. To me d(s,s') compare two coordinate pairs and I do not know how to relate it to the arccos you are using, i.e. what are x,y?
- could you measure the variance observed due to the sampling of anchor points and could you report whether the reconstruction error is greater further from anchor points?
- how does Nadaraya-Watson smoothing compare with respect to solving the low rank problem for each point?

References:
- you should at least refer to weighted low rank matrix approximation (Srebro & Jaakkola, ICML-03). It would be good to refer to prior work on expanding low rank matric approximation, given how fertile this field has been in the Netflix prize days (Maximum Margin Matrix Factorizations, RBM for matrix completion...).

Details along the text

- In Eq. 1, to unify notation, you could use the projection Pi here as well
- Hoelder continuity: I do not understand how it relate to the smoothing kernel approach defined below. I believe this sentence could be removed.