Matrix low rank approximation is one of the most classic dimension reduction methods in data analysis. The standard least squared error version can also be solved efficiently using the singular value decomposition, and we know how to do this in time comparable to the input sparsity (Clarkson & Woodruff, 2017). Despite its utility, natural variants of low-rank approximation turn out to be intractable. Weighted low-rank approximation is one well studied example: in many applications, some of the entries of a matrix may be less important to approximate than others (e.g., they might be known to be noisy), and thus we may have a weight associated with each entry. While standard least-squares regression for vectors can incorporate weights directly, the matrix version turns out to be challenging. Formally, the weighted low-rank approximation problem is defined as follows: given A ∈ R d×n , a non-negative weight matrix W ∈ R d×n and a parameter k, the goal is to find a rank k matrix L that minimizes Cost(L),
(1)
The problem and its difficulty were recognized as early as Young (1941), and it has been well-studied in the ML literature starting with the work of Srebro & Jaakkola (2003). Unlike the unweighted version (which corresponds to W = 1 d×n ) low-rank approximation, the problem above is NP-hard in general (Gillis & Glineur, 2011). Much of the early work such as Srebro & Jaakkola (2003); Manton et al. (2003); Eriksson & van den Hengel (2010) thus developed heuristics for the problem. The first provably efficient algorithms were obtained in the work of Razenshteyn et al. (2016) (see also references therein for work on matrix completion which is closely related). Razenshteyn et al. (2016) as well as more recent works (Musco et al., 2020;Ban et al., 2019b) assume that W has low rank, and develop algorithms that achieve a (1 + ) (multiplicative) approximation to the optimum cost, while having a running time exponential in the rank of W .
Very recently, Musco et al. (2020) initiated a study of additive error bounds for weighted low rank approximation.
Here the goal is to obtain an L such that Cost(L ) ≤ OPT + A 2 F , where OPT is the optimal cost. Additive error guarantees have been a classic notion in the literature on low rank approximation (starting with the seminal work of Frieze et al. (2004) on sampling for low rank approximation with additive error). Additive guarantees are realistic in applications where the optimal error is a small yet constant fraction of the total mass (e.g., when a low rank approximation may capture 90% of the Frobenius mass).
So far, our discussion has been restricted to error in the squared norm. However, low rank approximation has also been studied in entrywise p norms for p = 2. While any p > 0 ensures that the matrix L approximates A, the choice of p determines how the non-uniformity in approximation error is penalized. For example, an 1 penalty allows some errors |A ij -L ij | to be much larger than others (as long as the total sum is small), while as p → ∞, higher errors are penalized severely. Thus small values of p are used when some entries can be ignored as outliers (e.g., Candes & Recht (2008)), while higher values of p ensure a more uniform approximation.
The works of Song et al. (2017) and Ban et al. (2019a) develop sketching based algorithms for p norm approximation, particularly for p ∈ [1,2]. They aim to find low-rank approximations whose objective value is ≤ (1 + ) times the optimum. Chierichetti et al. (2017) develop approximation guarantees in much more generality, for all p ≥ 1 (including p = ∞). Their result gives a simple O(k log n) multiplicative approximation to the optimal error. Goals. Our goal in this paper is to consider weighted low rank approximation with 2 and p error objectives and develop efficient and practical algorithms. We prove the efficacy of the greedy procedure under a novel yet natural assumption and establish additive error guarantees.
In all our results, we assume that A is the input matrix, and that W is the non-negative weight matrix which has been re-scaled to satisfy W ij ∈ [0, 1] for all i, j.
Our first result is to develop a simple greedy algorithm that gives an additive error approximation to weighted lowrank approximation. Unlike prior work, our analysis does not require any explicit assumptions on the weight matrix itself. It works as long as the target matrix (the intended low rank approximation) has a Frobenius norm not too large compared to A. Formally, our theorem is the following: Theorem 1. Suppose there exists a rank k matrix L that satisfies the two conditions: (a) Cost(L) ≤ Γ and (b)
F for some parameters Λ, Γ. Then for any > 0, there exists an efficient algorithm that outputs a matrix L of rank at most O(kΛ/ 2 ) that satisfies
Remark. Note that the guarantee is not in terms of the optimal error but in terms of Γ. This is because we could have the optimal matrix L * having a large value of L * F , but there may exist an L with only a slightly larger cost, but a much smaller value of L 2 F . We also note that in the unweighted case (W = 1 d×n ), the bound on L F / A F is automatically satisfied: indeed, the ratio is always ≤ 1. However in the weighted case, there can be pathological cases where a low-rank approximation has a much higher Frobenius norm than A. As an example, consider the case of A = W = I n (n × n identity). The matrix L = 1 n×n (all ones) is a rank-one matrix that achieves zero weighted approximation error. However,
Informally, our assumption is equivalent to requiring that even the "unimportant" entries in A are not too different in magnitude from the corresponding entries in L, on average. We believe that this is a reasonable assumption when approximating A by L. Moreover, under this assumption, the theorem requires no structural assumptions on W (as in prior work).
Remark. It is natural to ask if a dependence on Λ is necessary in general. Showing lower bounds in terms of this parameter is an interesting open direction. However, we note that the known hardness results for matrix completion give an evidence for hardness when A, W are sparse (in this case, L F / A F is Θ(n)). Specifically, Hardt et al. (2014) show that for matrix completion, given a matrix A which is the restriction to indices Ω of a rank-k matrix L with entries of magnitude O(1), for any constant c, it is hard to construct a matrix B of rank r = ck such that
(This is assuming the hardness of an appropriate variant of coloring.) Viewing W as the binary mask matrix corresponding to Ω, this also shows the hardness of weighted low rank approximation. The catch is that the amount of additive error allowed above is quite small; it is A 2 F only when the matrix is sparse. The algorithm is a greedy procedure that iteratively adds a rank 1 matrix to a decomposition, similar to Frank-Wolfe methods (see, e.g., Clarkson (2010)). The crux of the analysis is in showing that in spite of potentially bad choices in the past, there exists an update that can significantly improve the decomposition. A powerful feature of our techniques is that we can extend them to weighted approximation with p norm error. We study the entrywise p version of the objective in (1), defined as
Here, additive error will correspond to an p analog of the Frobenius norm, X Fp := i,j |X ij | p 1/p . Theorem 2. Let p > 2, and suppose there exists a rank k matrix L that satisfies: (a) Cost p (L) ≤ Γ and (b) L p Fp ≤ Λ A p Fp for some parameters Λ, Γ. Then for any > 0, there exists an efficient algorithm that outputs a matrix L that satisfies Cost p (L )
We remark that this does not strictly dominate Theorem 1 because of the additional factor of k. For p = 2, this extra factor appears because the choice of basis for the target low-rank subspace is important to analyzing the greedy algorithm. As we discuss in Section 3, we need to use a carefully chosen basis for our argument.
Another remark is that our ideas only apply to p > 2. When p < 2, the maximization problem in each iteration of our current approach turns out to be that of computing the hypercontractive norm of a matrix, which is known to be hard (Barak et al., 2012;Ban et al., 2019a).
Our algorithm follows a similar outline as the one for Theorem 1, but it turns out to be much harder to analyze the improvement. We end up using tools from recent works on p regression (Adil et al., 2019;Bubeck et al., 2018). Moreover, finding a rank-one update in each step requires approximately computing the p → 2 operator norm of an appropriate matrix, which can be done efficiently for p > 2 using semidefinite programming, as shown by Nesterov (1998); Bhattiprolu et al. (2019).
Finally, as discussed in the introduction, even the unweighted version of low-rank approximation with entrywise p error has received a lot of interest, and is known to be challenging. Here, we obtain the following additive approximation.
Theorem 3. Let p > 2, and let OPT k denote the error of the best rank-k approximation of a given matrix A in the entrywise p norm. There exists an efficient (polynomial time) algorithm that outputs an
Unlike the previous theorems, this result is unconditional. Indeed, it is a simple consequence of Theorem 2 (see Section 3.4). But to the best of our knowledge, such an additive error approximation for p low rank approximation was not known for p > 2. Given known hardness results for purely multiplicative approximation, it is interesting to study additive error guarantees (see Ban et al. (2019a)).
Our algorithm for Theorem 3 can be viewed as extending the familiar iterative peeling algorithm for 2 low-rank approximation to the p setting, for p > 2. The iterative step is different (now involving a p → 2 norm computation), and we obtain an additive error guarantee. The theorem also complements the sketching-based algorithms for obtaining bi-criteria algorithms for p ∈ [1, 2) from Ban et al. (2019a). Finally, note that when the optimal error OPT k is very small
Fp , the algorithm of Chierichetti et al. ( 2017) has a better guarantee than Theorem 3.
All the matrix and vector notations used in the paper will be defined at first use. We begin in Section 2 with the greedy algorithm for the weighted Frobenius error. The framework is then extended to the case of weighted p norm error in Section 3. The case of unweighted p error (Theorem 3) follows as a corollary and is presented in Section 3.4.
We now present the greedy framework that underlies all of our algorithms.
Outline. Our algorithm proceeds by maintaining a low-rank approximation for A and iteratively adding a rank-1 component that ensures sufficient error reduction. This is done by finding a vector z and subtracting an appropriate multiple of z from the residuals of each column. The analysis proceeds in a column-by-column fashion, and thus we begin with a few useful lemmas about approximating a single column, and present Algorithm 1 and its analysis in Section 2.1.
Our analysis is similar in spirit to the analysis of the greedy algorithm for column subset selection and sparse coding, (Altschuler et al., 2016;Bhaskara & Tai, 2019), but we need a different view in order to incorporate weights for entries. We begin with a few lemmas about approximating a single column using a collection of vectors. Let a ∈ R d be a vector, and w ∈ R d be weights for the coordinates. Define the function f w : R d → R as:
where w i , a i , v i denote the ith entries of the corresponding vectors. Next, suppose that x is a vector (which will be our current approximation for a). Assume that x is "locally optimal" in the sense that increasing or decreasing the magnitude of x does not reduce the value of f w . Formally, x satisfies ∇f w (x), x = 0. The gradient has a simple form in our setting, ∇f w (v) = 2w • (a -v) (recall that • denotes the Hadamard or element-wise product). The following lemma shows how moving along a certain direction improves the value of f w . First, we define
which is the least possible value of f w that can be obtained by moving from x along the direction u. (As we can set η = 0, g w (x, u) is always ≤ f w (x).) Lemma 4. Let a, x, w be defined as above, and let u ∈ R d be a vector such that | ∇f w (x), u | ≥ γ and i w i u 2 i ≤ 1. Then we have
The proof follows by a direct expansion of f w , and we defer the details to the supplement.
Next, we show a lemma that is central to our argument. It says that if there is some u such that f w (u) < f w (x), and if u can be written as a linear combination of some basis vectors using "small" coefficients, then one of the basis directions can lead to a sufficiently large reduction in the value of f w . Formally, Lemma 5. Let u 1 , u 2 , . . . , u k ∈ R d be arbitrary vectors, and suppose u = j α j u j , where j α 2 j = B. Let a, x, w be defined as above, and suppose that f w (u) < f w (x). Then
Proof. We first observe that because of the convexity of f w (it is a non-negative sum of convex functions), we have that
The last equality is because of our assumption that scaling x will not improve
. Now, plugging in u = j α j u j and applying Cauchy-Schwartz, we obtain:
The first term is B by definition, and this completes the proof of the lemma.
The algorithm proceeds as follows: at time step t = 0, 1, . . . , an approximation x (t) j is maintained for every column a j . Unlike in the single column case above, we now have (potentially) different weight vectors w j for each column j. We thus define
where w j,r denotes the rth coordinate of w j (similarly for a j ). Since our goal is an additive error approximation, an ideal goal is to bring f j (v) within a j 2 2 of the optimal approximation for column j, for all j. (Algorithm 1 gives a full description of the procedure.)
Remark. Steps 7 and 8 of the algorithm involve a line search. This is easy in our case because the associated functions of η are univariate quadratics.
We start with some notation concerning the target rank-k solution L (as promised by the statement of Theorem 1). Suppose that L = U V T , where the columns of U are orthonormal, and let u j ∈ R d , v j ∈ R k denote the jth columns of U and V T respectively. Because of the orthonormal columns in U , we have v j 2 = L j 2 , where L j is the jth column of L. Our first goal is to obtain a column-wise control on L j / a j . Define the column j to be good if L j 2 / a j 2 ≤ Λ/ and bad otherwise. In what follows, we denote by G the set of all good columns. The following lemma is easy to see.
Algorithm 1 Weighted low rank approximation with L2 error 1: Input: Matrix A ∈ R d×n , error parameter 2: Output: Low-rank approximation L ∈ R d×n whose columns are spanned by a set of vectors Z, with |Z| = k := 8kΛ/ 2 . 3: Initialize Z = ∅, set x (0) j = 0 for all j 4: for t = 1, 2, . . . , k do 5: Using fj defined in (4), let z ∈ R d , z 2 = 1 be the vector that maximizes j ∇fj(x (t-1) j
), z 2 , and add z to Z 6:
for each j ∈ [n] do 7:
Compute η that minimizes fj(x Proof. Suppose the contrary, and assume that the inequality fails to hold. By the definition of bad, we have that
This contradicts our assumption about the bound on L The lemma allows us to focus on the good columns for most of our analysis. We now introduce the following notation to track the progress of the algorithm.
Notation. We denote
, θ
.
(5) Thus, informally, our goal is to ensure that θ (t) j ≥ δ jon average. We also study the following weighted averages:
where A G is the submatrix of A comprising only the good columns. The next lemma shows that if ψ (t) -δ * is large, then the (t + 1)th iteration makes considerable progress. Formally, Lemma 7. Suppose that after the t'th iteration of the algorithm we have ψ (t) > δ * . Then there exists a z such that j∈G | ∇f j (x
Proof. The idea will be to prove that one of the {u i } i∈ [k] satisfies the condition of the lemma. We do this by applying Lemma 5 to each of the good columns.
Step 8 ensures that the current representation for each column cannot be improved by rescaling, which is essential for applying Lemma 5. Consider any j ∈ G. This implies that L j can be written as i∈[k] α i u i , where i αfoot_0 i ≤ Λ a j 2 2 (indeed the α i are precisely the entries of the column v j ). Thus, by applying Lemma 5, we get
where (x) + = max(x, 0).
We first show that the sum of the RHS above over j ∈ G is large. By viewing
as a probability distribution over the indices j ∈ G and using the fact that
Using the observation that for any real numbers c, d, (c) + + (d) + ≥ (c + d) + (and generalizing this to a sum of multiple terms), the RHS above can be simplified (using ( 6)) as
The RHS is positive by assumption, and thus plugging the above back into (7), we get:
Thus, by averaging, there exists an index i that satisfies the conclusion of the lemma. This completes the proof.
The next lemma bounds the progress after t steps of the algorithm.
Lemma 8. Let < 1/2 be a given error parameter. The number of iterations needed to achieve
Proof. Recall that ψ (t) and δ * only involve the good columns. Define β t := ψ (t) -δ * , and note that β t clearly only reduces as t increases. We are done if β t ≤ 2 , and thus consider some t ≤ 8kΛ 2 and assume that β t > 2 .
We claim that in the next O(kΛ/ β t ) steps, the value of β t reduces by a factor 2. To see this, suppose the contrary. Now in each iteration, the algorithm finds some z with z = 1 such that the total leftover mass (over all the columns) reduces by at least the bound given by Lemma 7. This is because the algorithm finds z that maximizes j ∇f j (x (t-1) j
), z 2 , and by Lemma 4, this also quantifies the total mass reduction. (Note that we have used the fact that all the weights are ∈ [0, 1] when applying the Lemma.) Thus, since β t ≥ β t /2 for all the time steps t we are considering, the mass reduction is at least
where we used < 1/2 and Lemma 6. Thus if this continues for 8kΛ/ β t steps, the total mass reduction (which includes the reduction on bad columns) is ≥ β t A 2 F . But since β t > 2 and at most A 2 F of the mass is on the bad columns, this contradicts our assumption that β t did not reduce by a factor 2.
Thus, we have argued that as long as β t > 2 , it takes ≤ 8kΛ/ β t steps for β t to reduce to β t /2. Since β 0 ≤ 1, we have that it takes ≤ 2 j • 8kΛ steps for β t to reduce from 2 -j to 2 -(j+1) . Thus, as the geometric series converges to twice the last term, we have that β t reduces to ≤ 2 after 2 2 • 8kΛ steps, completing the proof of the lemma.
We can now complete the proof of Theorem 1.
Proof of Theorem 1. Lemma 8 gives us that after O kΛ 2 steps, we have ψ (t) -δ * ≤ 2 . Combined with Lemma 6, we have that the overall error in approximation is at most
. This completes the proof (after replacing by /3 throughout).
The high level outline of our algorithm is similar to the 2 setting. However, we need the right target decomposition, and need to set up the analysis carefully so as to make the rank-one update at every step efficient.
Let A be the matrix to be approximated and W the weight matrix as before. We make the same assumption: L = U V T is the target decomposition, and we have L Recall that the starting point in our analysis in the case of is rotation invariant (using a different basis U maintains the norm property). Unfortunately, this is not true in the case of p norms. A priori, it is not clear if there exists a good decomposition that allows a property such as the above for all the columns, nor is it clear what normalization one should choose for the columns of U . E.g., should they have
• p = 1, or a different norm such as 2 or the dual of p ?
So our first step is to describe the target decomposition and its properties. Lemma 9. Let L ∈ R d×n be any rank k matrix with k ≤ min{d, n}. Then there exists a decomposition
Proof. The proof uses the following simple observation about rank k matrices.
Observation. Let M ∈ R d×n be a rank k matrix. Then there exist a subset S of k columns of M with the property that all the other columns can be expressed as i∈S α i M i , with |α i | ≤ 1 for all i.
The observation follows by an extremal argument, considering the k columns such that the volume of the associated parallelopiped is maximized. We refer the reader to Chierichetti et al. ( 2017) (Lemma 2) for a proof. (The argument itself is classic, and the property above is related to the notion of an Auerbach basis in Banach spaces. See Taylor (1947); Martini et al. (2001). One of the early applications of this idea in the CS literature was in the work of Awerbuch & Kleinberg (2004).)
For our lemma, we apply the observation above to the matrix M whose columns are M j = Lj Lj p
. Let the chosen columns of M be denoted by the vectors u i , for i ∈ [k].
Then we have that all the other M j can be expressed as i α i u i with |α i | ≤ 1, and thus the corresponding L j can be expressed using coefficients |α i | ≤ L j p . By construction, the u i have • p = 1, which completes the proof of the lemma.
The lemma allows us to use the framework from Section 2 to develop an iterative algorithm.
The first main step is to obtain analogs of Lemmas 4 and 5 Let w, a ∈ R d , and define the function f w,p : R d → R as:
where w i , a i are the ith entries as before. Observe that the function f w,p is convex (as it is a sum of convex functions).
The key to our proof is an appropriate smoothness property for f , which we prove use the following lemma from Adil et al. (2019).
Lemma 10 (Lemma 4.5 of Adil et al. (2019)). Let y ∈ R and ∆ be any parameter. Then we have
where g is the derivative of |y| p , i.e., g = p|y| p-2 y, and γ p is the function (originally introduced in Bubeck et al. ( 2018)):
Using this lemma, we will be able to show the following analog of Lemma 4. Lemma 11. Let a, x, w be defined as above, and let u ∈ R d be a vector such that | ∇f w,p (x), u | ≥ γ ≥ 0 and i w i |u i | p ≤ 1. Then there exists η such that for some constant c p = O p (1),
.
The proof of the lemma relies on Lemma 10 and a careful analysis. We thus defer it to the supplement. Our analysis will also need an analog of Lemma 5 where f w is replaced by f w,p . This is immediate because the proof only relies on the convexity of f w , and thus also applies to f w,p .
Similar to the 2 case, we define
where w j is the weight vector for the jth column and w j,r denotes the rth coordinate of w j (similarly for a j ).
Algorithm. The algorithm for the p error case is precisely the same as before, but instead of working with the functions f j , we work with f j,p (when taking gradients). The main change is in Step 5 of the algorithm, where instead of finding a vector z that maximizes j ∇f j (x (t) j ), z 2 subject to z = 1 (which reduces to finding the top singular vector of an appropriate matrix), we now need to solve the following:
This can be re-written as finding a vector z that maximizes M z 2 2 subject to z p = 1, for an appropriate matrix M (which we can construct since we know x (t) j and f ). This is exactly the problem of computing the so-called p → 2 operator norm of the matrix M . The classic result of Nesterov (1998) shows that the problem admits a constant factor approximation. More recently, the work Bhattiprolu et al. (2019) obtains nearly tight factors for the problem. Both these algorithms are based on a semidefinite programming relaxation for approximating the operator norm, and crucially rely on p ≥ 2 in their analysis. We summarize these results as follows.
Theorem 12. (Nesterov, 1998;Bhattiprolu et al., 2019) For any p ≥ 2, there exists an efficient (polynomial time) algorithm for approximating the p → 2 operator norm of a matrix M to a factor only depending on p (which indeed turns out to be O( √ p) using the result of Steinberg ( 2005))
Specifically, the algorithm outputs a z with z p = 1, such that the objective value in (10) is Ω 1 p times the optimum.
Our analysis once again involves quantities δ j and θ (t) j , defined as follows:
We also define weighted averages as before:
The following lemma shows that as long as ψ (t) -δ * is large enough, the algorithm makes significant progress.
Lemma 13. Suppose that after the t'th iteration of the algorithm we have ψ (t) > δ * . Then there exists a unit vector z such that j∈G | ∇f j,p (x
Proof. The proof follows the structure of that of Lemma 7, and will show that one of the u i satisfy the conclusion of the lemma. Consider some good column j.
Our updates ensure that we can apply Lemma 5 (where f j is replaced by f j,p ). The value of Λ that we use in the lemma statement is the following: every coefficient used is ≤ L j p in magnitude, from Lemma 9. Since j is a good column, this is at most Λ 1/p a j p . As there are k terms, the sum of squared coefficients is bounded by k a j 2 p Λ 2/p . Plugging this in, and writing C = Λ 2/p for convenience, we obtain:
Thus, since f j,p (x
by definition, we have (after plugging in above and simplifying the exponent of
The second inequality uses the fact that p ≥ 2 and θ (t) j ∈ (0, 1]. Then, we can sum over the columns j ∈ G, and mimicking the idea from the proof of Lemma 7 (this time using a j p p / A G p F,p as the distribution), we get
Thus by averaging and plugging in the value of C, one of the u i must satisfy the conclusion of the lemma.
Given this lemma, the proof of Theorem 2 follows as before.
Proof of Theorem 2. We first observe that an analog of Lemma 8 also holds in the current setting, with two differences. The first is the change from kΛ to 2/p k 2 Λ 2/p in the coefficient for the improvement at each step. Secondly, we only solve the p → 2 norm problem approximately, and this adds an additional factor of p to the bound. Thus, the number of steps needed for the β t to halve is now O pk 2 Λ 2/p 2/p , and thus reducing to 2 requires number of steps equal to the bound in the statement of the Theorem.
Finally, observing that the bound on the total mass of the bad columns carries over to the p case, the theorem follows.
We now show how to deduce Theorem 3 using Theorem 2.
Proof of Theorem 3. We only need to check that the matrix achieving the optimal error (say L * ) satisfies the conditions of Theorem 2. This is true because
This implies that the assumption holds with Λ = 2 p .
In this section we evaluate our algorithm (wlra-iter) for weighted low rank approximation by comparing its performance with three baselines: (a) applying SVD to the matrix A (svd) (b) applying SVD to weighted matrix W • A (wsvd) (c) regularized weighted low rank approximation algorithm with sketching in Ban et al. (2019b) (rwlra-sk). In (c), we use the alternating minimization based algorithm provided in Ban et al. (2019b). We present experiments on synthetic data below and defer other results to the supplement.
We conduct two sets of experiments. In the first set, we vary the output rank k and show how the error changes for each algorithm. In the second set, we demonstrate how the error in each algorithm changes as the signal to noise ratio (SNR) varies: the signal is a low rank matrix and we add Gaussian noise to it. In each experiment, we measure the scaled error
where Z is the solution output by each algorithm (we note that in the experiments in Ban et al. (2019b), the objective value is plotted instead of the error thus our experiments are not comparable); we average results over 10 independent runs. We first generate 500×5 dimensional matrices M 1 , M 2 with random orthonormal vectors as columns and a diagonal matrix S with diagonal elements [1, 0.9, (0.9) 2 , (0.9) 3 , (0.9) 4 ] (normalized). Thus M = M 1 SM T 2 is a rank 5 matrix with M F = 1. In each experiment we create matrix A by adding a noise matrix N with N ij ∼ N (0, σ 2 ) to M . We set the sketch size parameter in rwlra-sk to 100 in all experiments. We generate weight matrices of 500×500 dimension with the following configurations.
• W 1 : Each element is sampled from the interval [0, 1] uniformly at random.
• W 2 : Elements corresponding to largest 50000 |A ij |s are set to 0, and 1 elsewhere.
• W 3 : The random binary matrix is first chosen by setting each entry to 1 with probability 0.1 and 0 otherwise. Following this, the first 100 columns of first 150 rows are set to 1.
In a setting with random weights (W 1 ), even simple baselines such as SVD achieve a small error as expected. However with semirandom weights (as in W 3 ), SVD performs much more poorly compared to a greedy approach.
In the first set of experiments, we plot the error of each algorithm with output rank k in the list (5,10,15,20,25,30,35,40,50,60). Here we fix σ = 0.005 (thus SNR ≈ 0.16) and λ = 0.05 for weight matrix setting W 2 and λ = 0.01 for weight matrix settings W 1 , W 3 in rwlra-wk. Figure 1 shows the error of each algorithm for different weight matrices.
In the second set of experiments, we plot the error of each algorithm as the SNR is increased from 0.0004 to 4. Here we fix k = 50 and λ = 0.005 for weight matrix setting W 1 and λ = 0.01 for weight matrix settings W 2 , W 3 in rwlrawk. We control SNR by changing σ appropriately. Figure 2 shows the error rates of each algorithm for different weight matrices. The results show the greedy procedure achieving small recovery error even in low SNR regimes.
In our supplement, we provide analogous results for four other choices of weight matrices as well as two real datasets. The full code is also provided.
We study a natural greedy algorithm for the weighted low rank approximation problem and establish novel additive error guarantees in 2 and p norms for p > 2 under a new, realistic, assumption on the target low rank matrix. Our algorithm is easy to implement and works well in practice, compared to natural baselines and previous approaches.
error was to decompose L as U V T using the SVD, so that we have a U with orthonormal columns, and a V such that L j = v j . Implicit here is the fact that the 2 norm