Low Rank Approximation with Entrywise $\ell_1$-Norm Error

1.1 Our Results

• An O(nnz(A) + n·poly(k))-time algorithm achieves a (log d)·poly(k)-approximation for every k.By symmetry, the authors assume d ≤ n; when nnz(A) ≥ n·poly(k), this running time is optimal up to a constant factor for relative-error algorithms.Source: §1.1 · p. 5
• For constant k, a different algorithm achieves an O(1)-approximation in polynomial time, and a bicriteria algorithm returns rank 2k with an absolute-constant approximation.A rank-k version with the same factor requires the additional assumption that the output entries are integers in a polynomially bounded range.Source: §1.1 · pp. 5–6
• Under ETH, no polynomial-time algorithm achieves a (1 + 1/log^(1+γ)(n))-approximation for any arbitrarily small constant γ > 0, even when k = 1.This strengthens the NP-hardness result of [GV15].Source: §1.1 · p. 6
• For ℓ1 column subset selection, some matrices require a k^(1/2−γ) approximation from any poly(k)-column subset, while O(k log k) columns suffice for O(√(k log k))-approximation.The paper also gives a polynomial-time algorithm selecting O(k log k) columns for an O(k log k log d)-approximation, and extends the results to CUR with O(k log k) rows and columns and a poly(k) log d approximation.Source: §1.1 · p. 6
• For 1 ≤ p < 2, the paper gives the first provable ℓp low-rank approximation algorithms, including an nnz(A) + n·poly(k)-time algorithm with a (log d)·poly(k) ratio.It also gives the first low-rank approximation result under the sum of row-wise earthmover distances, with a (log^2 d)·poly(k) ratio; it does not provide the nonnegative factorization some applications require.Source: §1.1 · p. 6
• In the arbitrary-partition distributed model, an eO(snk)-communication protocol achieves a poly(k, log n) approximation; in turnstile streaming, eO(nk) + poly(k) space achieves the same ratio.Both are optimal for that approximation factor up to the stated polynomial factors, and the algorithms use eO(dk) random bits.Source: §1.1 · p. 7

1.2 Technical Overview

• The technical approach sketches with Cauchy random variables: truncation and expectation bounds yield an O(log d) guarantee, and row-wise ℓ1 projection onto the sketch span leads to a log d·poly(k) approximation.The initial sketch places a good solution in the span of SA; with O(k log k) rows, it controls contraction on the U* column span, while the analysis bounds the optimal solution's sketch cost. The overview also describes a poly(k log n)-approximation construction and sparse Cauchy matrices for reducing runtime.Source: §1.2 · pp. 7–9
• For small k, enumerating O(k log k) sampled rows leads to an eO(k)-approximation and an O(1)-approximation when k is constant.Existentially, O(k log k) rows contain an O(√(k log k))-approximation, whereas the polynomial-time selection guarantee is O(k log k log d).Source: §1.2 · pp. 9–10
• With poly(k) selected rows, the best ℓ1 approximation can have ratio k^(1/2−γ), and some matrices admit no better than a (2 − Θ(1/d))-approximation within their full row span.The row-selection hard instance combines k Gaussian columns with an identity matrix; the full-row-span result is separate.Source: §1.2 · pp. 10–11
• A rank-2k bicriteria output achieves an absolute-constant approximation, using an initial rank-k approximation and a sampled, enumerated subproblem.The initial approximation may have a factor between 1 and poly(n); the final bound is ∥A − bA∥1 ≤ C · OPT.Source: §1.2 · p. 11
• A Cauchy-sketch construction yields a log d · k · log^2 k lower bound, while a related k^(1/2−γ) lower bound applies to any oblivious sketching matrix.The Cauchy construction is optimized from a log d · poly(k) lower bound.Source: §1.2 · p. 12
• An eO(d)-wise independent Cauchy sketch gives a poly(k) log d approximation in its span and supports distributed communication of eO(kd) bits independent of n.The distributed and streaming algorithms follow approaches for Frobenius-norm low-rank approximation; the passage also describes limited-independence methods.Source: §1.2 · p. 12
• Under ETH, no polynomial-time algorithm achieves a (1 + 1/log^(1+γ) n)-approximation, and four named heuristics can have approximation ratio n^min(γ,0.5−ϵ) at rank 3.The ETH reduction modifies the [GV15] hard instance and plants it in a larger matrix padded with tiny values.Source: §1.2 · pp. 12–13

1.3 Several Theorem Statements, an Algorithm, and a Roadmap

• The stated guarantees include a rank-k (log d) poly(k)-approximation in nnz(A) + (n + d) · poly(k) time and a rank-k CUR approximation with factor eO(k).Both algorithms succeed with probability 9/10; the CUR algorithm takes poly(n)d eO(k)2 eO(k^2) time.Source: §1.3 · p. 13
• For every k ≥ 1 and constant c ≥ 1 with n = k^c, some matrix requires Ω(k^(0.5−α)) error ratio for approximations in the span of n/2 rows.Here α > 0 is an arbitrarily small constant; the roadmap assigns later sections to algorithms, extensions, hardness, limited randomness, distributed and streaming results, and experiments.Source: §1.3 · pp. 13–14

B.1 Polynomial system verifier

• The appendices define notation and polynomial-system verification, introduce Cauchy and p-stable transforms, and present Lewis weights and their computation.The stated Lewis-weight algorithm computes C-approximate ℓp Lewis weights in O((nnz(A) + d^ω log d) log n) time for n ≥ d, 4 > p ≥ 1.Source: A Notation · p. 15, §B.1 · p. 15

B.3 Lewis weights

• Lewis-weight sampling uses N=O(d log d) for p=1, O(d log d log log d) for 1<p<2, and O(dp/2 log d) for 2≤p<4; the appendix also gives an n poly(d)-time construction.The construction uses eO(d) nonzero entries.Source: §B.3 · pp. 16–17

B.4 Frobenius norm and ℓ2 relaxation

• For 1≤p<2, the appendix states a Frobenius-norm relaxation claim for ℓp-low-rank approximation.The supplied passage does not include the claim’s bound.Source: §B.4 · p. 18

B.5 Converting entry-wise ℓ1 and ℓp objective functions into polynomials

• Absolute-value constraints can be converted to an equivalent problem with O(m) extra constraints and m extra variables, while rational-p objectives use O(m) extra constraints and variables.The latter conversion applies when p=a/b for positive integers a and b.Source: §B.5 · pp. 18–19

B.6 Converting entry-wise ℓ1 objective function into a linear program

• Minimizing the entrywise ℓ1 error over U in min ||UB−A||1 can be formulated as a linear program with O(nd) constraints and O(nd) variables.Source: §B.6 · p. 19

C ℓ1-Low Rank Approximation

• The main algorithm section covers existence results, approximation algorithms, CUR decomposition, and useful properties of ℓ1-low-rank approximation.Its rank-r algorithm, with r set to poly(k), is used as a black box in several other algorithms.Source: C ℓ1-Low Rank Approximation · p. 19

C.1 Existence results via dense Cauchy transforms, sparse Cauchy transforms, Lewis weights

• A dense Cauchy transform gives an O(√k log k log d)-approximation with m = O(k log k) in polynomial time.The theorem states success probability 9/10.Source: §C.1 · pp. 19–20
• A sparse Cauchy transform gives an O(k^4.5 log^4.5 k log d)-approximation with m = O(k^5 log^5 k) in polynomial time.The theorem states success probability 9/10.Source: §C.1 · pp. 19–20
• Lewis-weight sampling gives an O(√k log k)-approximation using m = O(k log k) samples.The stated running time is T = (nd)^{~O(k)}.Source: §C.1 · p. 20
• The existence corollary places a rank-k approximation A′ in the row span of a sampled-and-sketched matrix S′A, itself within the row span of A.Its error is bounded by α times the optimal rank-k entrywise ℓ1 error.Source: §C.1 · p. 21

C.2 Input sparsity time,

• The algorithm is worse than the one in the next section, but is easy to extend to distributed and streaming settings.The paper points to Sections K and J for those extensions.Source: §C.2 · p. 22
• Dense Cauchy sketches give αs = O(√k log k log d) but take O(s nnz(A)) time for SA; sparse sketches give αs = eO(k^4.5 log d) and compute SA in nnz(A) time.For the right sketch, dense transforms give αr = O(log n) with O(r · nnz(A)) time, while sparse transforms give αr = eO(k^2) log n with O(nnz(A)) time.Source: §C.2 · p. 22
• With probability 9/10, the sparse-sketch algorithm achieves a poly(k) log(n) log^2(d)-approximation in O(nnz(A)) + (n + d) poly(k) time.The algorithm uses sparse Cauchy transforms to keep sketch computation linear in the number of nonzeros.Source: §C.2 · pp. 22–23
• A slower alternative uses nd·poly(k) + (n + d)·2^~O(k^2) time and has a much smaller poly(k) factor in its approximation ratio than Theorem C.3.It uses a polynomial system verifier at the final optimization step; the paper says this improves the approximation ratio at the cost of exponential dependence on k.Source: §C.2 · p. 24

• The procedure initializes UB and VB from a Frobenius-error minimization, sets r = O(k log k), and then takes the best solution.Source: §C.2 · p. 29

C.5 Rank-2k and O(1)-approximation algorithm for an arbitrary matrix A

• An arbitrary matrix admits an O(1)-approximation with rank 2k in (nd)^{~O(k^2)} time.The algorithm enumerates guesses and returns a factorization among them.Source: §C.5 · pp. 29–30
• The rank-2k method discretizes U* after choosing an ℓ1-well-conditioned basis, leaving polynomially many possibilities per entry.Entries below the stated threshold can be replaced by zero with additive error at most OPT/100.Source: §C.5 · pp. 29–30
• For entries bounded by poly(n), a rank-k O(1)-approximation takes (nd)^{~O(k^3)} time.The method guesses Lewis weights and DU*, then solves the remaining regression problems by linear programming.Source: §C.5 · pp. 30–31
• Guessing the Lewis-weight sampling matrix D is feasible because its support has at most n^{O(t)} choices for t = O(k log k), and rounding probabilities keeps the approximation loss constant.The total number of candidate D matrices is stated as n^{~O(k)}.Source: §C.5 · pp. 30–31

C.6 CUR decomposition for an arbitrary matrix A

• The construction applies Lewis-weight sampling to rows and columns, with O(k log k) nonzero diagonal entries in each sampling matrix.The proof states constant-factor approximation bounds for the two sampled stages.Source: §C.6 · pp. 31–33
• The CUR algorithm returns rank(CUR) = k using O(k log k) columns and O(k log k) rows selected from A.The theorem states success probability 9/10.Source: §C.6 · pp. 31–32
• Its running time is O(nnz(A)) + (n + d) poly(k).The decomposition uses C = AD2 and R = D1A, with the middle factor formed from sampled-and-rescaled matrices.Source: §C.6 · p. 33

C.7.1 Properties

• For a rank-r matrix B, Theorem C.19 gives an algorithm taking (n + d)·poly(k) time to output factors U and V, with its guarantee holding with probability 9/10.The supplied theorem statement does not include the approximation bound.Source: §C.7.2 · p. 35
• The analysis bounds a sketched rank-k objective by O(r^1.5 log^1.5 r)·OPT.This bound is for min over U and Z of ∥UZSB − B∥1.Source: §C.7.2 · p. 36
• Lemma C.20 gives a poly(r)-approximation for the sketched factorization objective, with probability at least .999.Its objective compares ∥BRX′·Y′SB − B∥1 with the minimum over X and Y of ∥BRXY SB − B∥1.Source: §C.7.2 · p. 37

D.1 Definitions

• A restricted-multiple-regression-cost-preserving sketch is defined by preserving the rank-k regression cost up to a factor c^8.Source: §D.1 · p. 38

D.2 Properties

• Sketches satisfying dilation and contraction conditions preserve multiple-regression and restricted low-rank costs within a factor 2c1c2 + 1.The restricted guarantee applies to rank-k candidates meeting the stated sketched-cost condition; a two-sided sketch is analyzed by applying the restricted result successively to both sketch matrices.Source: §D.2 · pp. 39–41
• For the stated dilation and contraction guarantees, row-sampling, dense and sparse Cauchy, and limited-independence Cauchy sketches have different row-count and c1c2 bounds.Sampling m = O(t log t) rows by ℓ1 Lewis weights gives c1c2 = O(1). Dense Cauchy gives O(log d) for m = O(t log t), while sparse Cauchy gives O(t2 log2 t log d) for m = O(t5 log5 t). Limited-independence Cauchy gives O(t log d) with W = eO(d), or O(log d) with W = eO(td), for m = O(t log t).Source: §D.2 · p. 42

D.3 Cauchy embeddings, no dilation

• A rescaled Cauchy sketch controls the sketched error of the optimal low-rank residual with probability at least 99/100, using a logarithmic-in-dimension proof parameter.The proof chooses t = Θ(log d) when k ≤ d and m = poly(k).Source: §D.3 · pp. 42, 44

D.4 Cauchy embeddings, no contraction

• For m = O(k log k), a rescaled i.i.d. Cauchy sketch gives a constant-factor lower bound on the sketched residual for all V with probability at least 0.95.The guarantee fixes an optimal U* and concerns ∥SU*V − SA∥1 relative to ∥U*V − A∥1.Source: §D.4 · p. 44

D.5 Cauchy embeddings, k-dimensional subspace

• For an ℓ1 well-conditioned basis, a rescaled Cauchy matrix with t = O(k log k) rows preserves all subspace vectors with probability 99/100.The stated bounds give a lower bound ∥SUw∥1 ≳ ∥Uw∥1 and an upper bound O(αβ log k)∥Uw∥1 for all w, under the stated well-conditioned-basis conditions.Source: §D.5 · pp. 45–46
• The k-dimensional subspace result uses t = O(k log k) rows of independently sampled, rescaled standard Cauchy entries and states a probability-.99 guarantee.Its proof uses a well-conditioned basis and a prior lemma to relate the norms before rescaling.Source: §D.5 · p. 47

D.6 Sparse Cauchy transform

• The sparse Cauchy-transform section proves no-dilation and no-contraction results, with stated probability at least .999 for its transform lemmas.For the cited construction, m = O(k^5 log^5 k) and σ = O(k^2 log^2 k), according to [MM13].Source: §D.6 · pp. 47, 49

D.7 ℓ1-Lewis weights

• With m = O(k log k) Lewis-weight samples, the section establishes probability-.99 guarantees for all V in the stated sampling-and-rescaling lemmas.Lemma D.31 and Lemma D.32 concern sampling according to the Lewis weights of U*; D.32 uses the optimal factorization U*, V* of A.Source: §D.7 · pp. 50–51

E ℓp-Low Rank Approximation

• For ℓp-low rank approximation, the paper states that all described ℓ1 algorithms extend directly, supported by fundamental lemmas whose proofs largely match Section D.The section states only its important lemmas because most proofs are identical to those in Section D.Source: E ℓp-Low Rank Approximation · p. 51

E.1 Definitions

• The ℓp definitions formalize dilation, contraction, subspace embeddings, and multiple-regression-cost-preserving sketches, including a restricted version for low-rank regression.These definitions are given for 1 < p < 2.Source: §E.1 · p. 51

E.2 Properties

• A sketch with c1-dilation on the optimal residual and c2-contraction on the input subspace yields a multiple-regression-cost-preserving guarantee with factor 2^(p−1)(2c1c2 + 1).Source: §E.2 · p. 53

E.4 Dense p-stable transform

• For dense p-stable sketches with m = O(t log t), the product c1c2 is O(log d).Source: §E.2 · p. 55

E.5 Sparse p-stable transform

• For sparse p-stable sketches, m = O(t^5 log^5 t) gives c1c2 = O(t^(2/p) log^(2/p) t log d), while a larger dimension-dependent choice also gives a bound involving r.The latter choice is m = O((t + r)^5 log^5(t + r)); its stated bound is O(min(t^(2/p) log^(2/p) t log d, r^(3/p) log^(3/p) r)).Source: §E.2 · p. 55

E.6 ℓp-Lewis weights

• Sampling and rescaling O(t log t log log t) rows by ℓp Lewis weights gives c1c2 = O(1).Source: §E.2 · p. 55

E.3 Tools and inequalities

• A well-conditioned basis has bounded p-norm and controls the q-norm of coefficient vectors, with conditioning parameters that are low-degree polynomials in k and independent of n.Source: §E.3 · p. 56

F.1 Definitions

• The paper introduces an embedding of EMD into ℓ1 and defines EMD-based distances for vectors and matrices, including a column-based matrix distance.Source: F EMD-Low Rank Approximation · p. 59, §F.1 · p. 60

F.2 Analysis of no contraction and no dilation bound

• Theorem F.3 gives a poly(k,n,d)-time algorithm with error at most poly(k)·log d·log n times the rank-k optimum, holding with probability .99.Source: §F.2 · p. 61
• The proof reduces EMD approximation to ℓ1-low-rank approximation using a sketch with m = poly(n), then applies the ℓ1 algorithm.Source: §F.2 · p. 61
• Using a row-based rather than column-based ∥·∥1,EEMD distance yields a slightly better result when applying the ℓ1-low-rank algorithm.Source: §F.2 · p. 61

G Hardness Results for Cauchy Matrices, Row Subset Selection, OSE

• The section roadmap says the later hardness results use random Cauchy matrices and address row subset selection and oblivious subspace embeddings.Source: G Hardness Results for Cauchy… · p. 61

G.1 Hard instance for Cauchy matrices

• With probability .99, for 1 ≤ t = o(log d), a Cauchy sketch has error at least Ω(log d/(t log t)) times the best rank-k error on a constructed matrix.The theorem allows any Cauchy scale and any constant c < 1/3; its proof concludes with a total cost of Ω(d log d/(t log t)).Source: §G.1 · pp. 62, 66

G.2 Hard instance for row subset selection

• For row-subset approximation, achieving cost at most (2 − ε)(d − 1) requires selecting Ω(εd) rows in the constructed matrix.The matrix has an all-ones first column and an identity matrix in its remaining columns.Source: §G.2 · pp. 66–67
• The eight-case analysis completes the row-subset-selection proof, with cost lower bounds of 2C for C ≥ 2 and 2(C′(C′ − 1)) for C′ ≥ 2.For C = 1 or C′ = 1, the stated lower bound is 0.Source: §G.2 · p. 71

G.3 Hard instance for oblivious subspace embedding and more row subset selection

• By Yao’s minmax principle, proving Theorem G.27 suffices to prove Theorem G.31.Source: §G.3 · p. 71

G.3.1 Definitions

• The definitions subsection introduces total variation distance and Kullback-Leibler divergence, and states Pinsker’s inequality and a Gaussian tail bound.Source: §G.3.1 · p. 71
• It also states that projecting an i.i.d. standard Gaussian matrix onto a matrix with orthonormal columns preserves the i.i.d. standard Gaussian distribution.Source: §G.3.1 · p. 72
• The subsection further lists the matrix determinant lemma, a Gaussian KL-divergence lemma, and the Sherman-Morrison formula.Source: §G.3.1 · p. 72

G.3.2 Main results

• For bounded-ℓ1 vectors with coordinate magnitudes at most 1/k^β, the Gaussian projection has at most O(k/log k) coordinates of magnitude at least on the order of 1/log k, except with probability 2^−Θ(k).The lemma assumes β > γ > 0 and β+γ < 1; its proof bounds the contribution from vectors split into magnitude ranges and applies a union bound.Source: §G.3.2 · pp. 75, 77, 78
• If the stated event holds, then with probability at least 1−2^−Θ(tk), at least ⌈t/10⌉ vectors cannot be simultaneously approximated by Ax and Vx with both ℓ1 costs below Ω(k^(0.5−α)).The event uses β = 0.5+α/2 and γ = 0.5−α, for arbitrarily small constant α ∈ (0, 0.5).Source: §G.3.2 · p. 78
• For constant γ = 0.5−ε, where ε > 0 can be arbitrarily small, the approximation gap is at least Ω(k^γ), equivalently Ω(k^(1/2−ε)).Source: §G.3.2 · p. 81
• Theorem G.28 states that, with positive probability, no algorithm achieves its row-span fitting guarantee using n/2 rows, for n=O(k^c) and arbitrarily small constant α∈(0,0.5).Source: §G.3.2 · p. 82
• Under Theorem G.31’s stated embedding condition, the embedding dimension must satisfy r=Ω(k^(c2-2c1-2)).The theorem assumes k≥1, γ∈(0,0.5), arbitrary constants c1,c2>0, and min(n,d)≥Ω(k^c2).Source: §G.3.2 · p. 84
• Theorem G.27, G.28, and G.31 remain valid when their approximation ratio is √k/log^c k for a sufficiently large constant c.Source: §G.3.2 · p. 85

H Hardness

• The hardness section covers NP-hardness for a multiplicative error, stronger ETH-based hardness, and an extension from rank 1 to rank k.Source: H Hardness · p. 85

H.1 Previous results

• For A∈{−1,+1}^(n×d), computing ∥A∥∞→1 is equivalent to finding its best rank-1 ℓ1 approximation, and this norm computation is NP-hard [GV15].Source: §H.1 · pp. 85–86

H.2 Extension to multiplicative error ℓ1-low rank approximation

• The section’s stated strengthening is that NP-hardness remains even when the goal allows some multiplicative error.The theorem statement is introduced for a ±1 matrix and vectors x and y.Source: §H.2 · p. 86
• The reduction distinguishes graphs with a cut of size at least c from graphs whose maximum cut has fewer than c edges through lower and upper bounds on ∥A∥∞→1.The bounds are stated in Claims H.8 and H.9, which reproduce the reduction from [GV15].Source: §H.2 · pp. 86–87
• The value of T decides whether the MAX-CUT instance has a cut of size at least c, so polynomial-time computation would solve an NP-hard decision problem.The reduction constructs a block matrix using edge endpoints and Hadamard blocks.Source: §H.2 · pp. 86, 88

H.3 Using the ETH assumption

• The proof uses ETH in the form that 3-SAT on r variables cannot be solved in O(2^δr) time for some δ > 0.The gap distinction is the route from the assumed approximation algorithm to a subexponential MAX-CUT algorithm.Source: §H.3 · pp. 88–89
• ETH rules out a polynomial-time algorithm for the theorem’s approximation task on ±1 matrices, as stated in Theorem H.13.The proof assumes a (1 + 1/W)-approximation with W = log^(1+γ) d and derives a contradiction.Source: §H.3 · pp. 88–89
• Distinguishing graphs with a cut of at least a|E| edges from graphs whose cuts all have at most b|E| edges in 2^o(|V|) time contradicts the cited MAX-CUT hardness theorem.The theorem gives constants a > b for 5-regular graphs.Source: §H.3 · pp. 88, 89, 91
• The reduction encodes a graph with |E| = O(|V|) as a block matrix in {−1, +1}^(n×d), with n = p|E| and d = p|V|.Each edge-vertex block is either constant-valued at its endpoints or a Hadamard matrix elsewhere.Source: §H.3 · p. 89

H.4 Extension to the rank-k case

• The first n coordinates of a selected column of the rank-k approximate solution give a rank-1 C-approximation to the original matrix.The reduction extends the lower bound from rank one to general k ≥ 1 under ETH.Source: §H.4 · p. 91
• For the augmented instance, the rightmost k−1 columns of the approximate solution form a rank-(k−1) matrix.The construction uses a block-diagonal matrix with a parameter B, under the stated entry-bound and constant conditions.Source: §H.4 · p. 91

I.1 Notations and tools

• Poly(k, d)-wise independent Cauchy variables suffice instead of fully independent variables to optimize the distributed algorithm’s communication complexity.The section introduces lemmas and tools for limited independent Cauchy variables.Source: §I.1 · p. 94, I Limited Independent Cauchy Random… · p. 94

I.2 Analysis of limited independent random Cauchy variables

• The analyzed Cauchy sketches use t = O(k log k) rows; limited independence within rows supports guarantees for a vector and a set of vectors, each with probability at least .999.The stated row-wise independence differs between the vector and set-of-vectors lemmas.Source: §I.2 · p. 95

J Streaming Setting

• The streaming section covers both row-update and turnstile settings, with separate algorithms for the two models.The turnstile algorithms are presented in the next subsection.Source: J Streaming Setting · p. 98

J.1 Definitions

• In the row-update model, each row arrives once in arbitrary order; in the turnstile model, updates increment individual matrix entries, and both permit a single pass.The streaming algorithm stores information about the matrix during the pass.Source: §J.1 · p. 98

J.2 Turnstile model, poly(k, log(d), log(n)) approximation

• The turnstile algorithms achieve poly(k, log(d), log(n)) approximation with constant probability, using poly(k) + eO(kd) words for subspace output and poly(k) + eO(k(d+n)) words for decomposition.The subspace guarantee is stated as an inequality against the best rank-k subspace fit; the decomposition algorithm returns factors.Source: §J.2 · p. 99

J.3 Row-update model, poly(k) log d approximation

• In row-update streaming, the subspace version achieves a poly(k, log(d), log(n))-approximation with constant probability using poly(k)+eO(kd) words.The proof gives the approximation bound for the output subspace matrix V*; the theorem states the space bound.Source: §J.3 · p. 101
• The row-update decomposition version achieves a poly(k) log d approximation with constant probability using poly(k)+eO(k(n+d)) words.The algorithm maintains C and computes U*=C bU at the end.Source: §J.3 · p. 102

K.1 Definitions

• The distributed setting defines row partitioning as vertically stacking machine matrices and arbitrary partitioning as A=sum_i Ai, with communication only between machines and a coordinator.Each transmitted word has O(log(snd)) bits.Source: §K.1 · p. 102

K.2 Arbitrary-partition model, subspace, poly(k, log(d), log(n)) approximation

• For arbitrary-partition data, the subspace protocol gives a poly(k, log(d), log(n))-approximation with constant probability and communicates s(poly(k)+eO(kd)) words.Source: §K.2 · p. 104

K.3 Arbitrary-partition model, decomposition, poly(k, log(d), log(n)) approximation

• For arbitrary-partition data, the decomposition protocol achieves a poly(k, log(d), log(n))-approximation with constant probability and communicates s(poly(k)+eO(k(d+n))) words.The protocol sends the machine-level Ui matrices to the coordinator to form U*.Source: §K.3 · pp. 105–106

K.4 Row-partition model, subspace, poly(k) log d approximation

• For row-partitioned data, the subspace protocol achieves a poly(k, log(d), log(n))-approximation with constant probability and communicates s(poly(k)+eO(kd)) words.Source: §K.4 · p. 106

• Each machine computes Li = T1iBiR, Ni = SiBiT2, and Mi = T1iBiT2, then sends these quantities to the coordinator.Source: §K.4 · p. 107
• The workflow sends bX to machines, which compute its SVD and V*; an optional decomposition branch computes U* and sends resulting values to the coordinator.Source: §K.4 · p. 107

K.5 Row-partition model, decomposition, poly(k) log d approximation

• The returned factors satisfy ||A − U*V*||_1 ≤ poly(k) log d times the optimal rank-k factorization error.The proof identifies U*V* as the protocol's approximation to A.Source: §K.5 · p. 108
• With constant probability, Algorithm 11 with decomposition solves the row-partition problem using s(poly(k) + eO(k(n + d))) words of communication.The coordinator holds U* and V* when the protocol terminates.Source: §K.5 · p. 108
• The protocol's correctness follows by sending Ui so the coordinator can compute U* and form U*V* = BR bXSB.The proof states that this product gives a poly(k) log d ℓ1-norm rank-k approximation to A.Source: §K.5 · p. 108

L.1 Setup

• Experiments used R 3.0.2 on a single-threaded Linux Ubuntu 14.04.5 LTS machine with an Intel X5550@2.67GHz CPU and 24G memory.Source: §L.1 · p. 108

L.2 Counterexample for [DZHZ06]

• On its constructed rank-1 input, [DZHZ06] incurs cost at least Ω(n^2) against an optimum of at most n^1.5+ϵ, giving a ratio no better than n^0.5−ϵ.Source: §L.2 · p. 108

L.3 Counterexample for [BDB13]

• [BDB13] can fit the first column alone, costing (n−1)^2 against an optimum of at most n^1.5, for a ratio no better than n^0.5.The counterexample traces how its recursive procedure reaches a matrix on which it fits that column.Source: §L.3 · pp. 109–110

L.4 Counterexample for [Kwa08]

• On constructed rank-2 inputs, [Kwa08] has an approximation ratio no better than Θ(n), although the optimum is at most n^1.5.The example’s interpolation cases incur costs of at least 2n^2.Source: §L.4 · pp. 111–112

L.5 Counterexample for [KK05]

• Top-singular-vector initialization yields a Θ(n) ratio, while random initialization can incur at least n^(c−1) for c≥2.For the top-singular start, the support remains fixed after iteration and the cost is at least (n−1)^2 against an optimum of at most n.Source: §L.5 · p. 114

L.6 Counterexample for all

• For the constructed rank-3 input, all four heuristics have approximation ratio at least n^min(γ,0.5−ϵ); experimentally, other algorithms’ residual costs grow faster than ours.Most algorithms, including ours, run in under 3 seconds, while and runtimes grow quickly with n.Source: §L.6 · pp. 114–115

L.7 Discussion for Robust PCA [CLMW11]

• At λ=1, the block-diagonal example permits equal objective values for outputs of rank k/2 and k, and the relative error may be arbitrarily bad.The objective may return the first k/2 blocks or A itself, both at cost kb.Source: §L.7 · p. 115
• For λ=1/√n and A=H_n, taking any number i of rows gives the same objective value n^1.5, while the relative error may be arbitrarily bad.Source: §L.7 · p. 115