Relative Error Tensor Low Rank Approximation

1 Introduction

• Assumption-free tensor relative-error approximation was unresolved, despite tensors’ applications to higher-order data, because rank-k optima may not exist and tensor-rank computation is NP-hard.The paper frames its goal as achieving provable algorithms without assumptions on the tensor itself.Source: §1 · pp. 5–6

1.1 Our Results

• Rank-O((k/ε)^(q−1)) bicriteria tensors achieve (1+ε) relative error in nnz(A)+n·poly(k/ε) time, with arbitrarily small additive error if no optimum exists.The guarantee is measured against rank-k tensors; the stated third-order algorithm succeeds with probability at least 2/3.Source: §1.1 · p. 7
• For bounded-norm factors, a rank-k solution runs in O(nnz(A)+n·poly(k,1/ε)+2^O(k²/ε))·n^δ time and permits a (1+ε)-approximation to OPT’s value.When a rank-k optimum does not exist, the result assumes a near-optimal rank-k tensor with bounded factors; the output tensor has an additive 2^-O(n^δ) error.Source: §1.1 · p. 8
• Tensor CURT obtains (1+ε) Frobenius error with optimal subset sizes, while matrix CUR achieves the guarantee in O(nnz(A))+(n+d)·poly(k,1/ε) time.A bicriteria tensor CURT alternative avoids the exponential-in-k²/ε time term but uses suboptimal subset sizes and core rank.Source: §1.1 · p. 9
• For entrywise ℓ1, ℓp (0<p<1), and asymmetric norms, algorithms achieve rank eO(k²) and poly(k,log n) approximation, with runtimes varying by norm.Rank-k and CURT variants are also available for these norms, with extensions to additional asymmetric norms and M-estimators.Source: §1.1 · p. 9
• Weighted tensor approximation runs in (nnz(A)+nnz(W)+n²·eO(r²k²/ε))·n^δ time under the stated bounded-factor assumption.The weight tensor has r distinct rows and columns; the result outputs three n×k factor matrices.Source: §1.1 · p. 9
• Unless ETH fails, distinguishing tensor rank at most k from at least c0·k requires 2^Ω(k^(1−o(1))) time; rank-1 relative approximation also has an ETH-based time lower bound.Under random-ETH, the rank-hardness exponent can be strengthened to k; the rank-1 lower bound rules out 2^o(1/ε^1/4) time.Source: §1.1 · p. 9

1.2 Our Techniques

• Many proofs use an “iterative existential proof,” which the authors turn into algorithms in different ways for the bicriteria and rank-k results.Source: §1.2 · p. 10
• Iterative factor-space updates resolve incompatible factor-span candidates and yield a rank O(k^2/eps^2) approximation in nnz(A) + n poly(k/eps) time.The iterative existential framework also supports low-rank approximation for other robust error measures.Source: §1.2 · pp. 10–12
• With factor entries bounded by 2^poly(n), rank-k output is obtained by minimizing a degree-6 polynomial over O(k^2/eps) indeterminates, at exponential-in-parameter cost.The factors are parameterized by indeterminate matrices, and the polynomial minimization runs in polynomial time in n under the stated bounded-entry assumption.Source: §1.2 · pp. 11–12

1.3 Other Low Rank Approximation Algorithms Following Our Framework.

• Tensor leverage-score sampling avoids materializing tensor-product matrices and enables column, row, and tube selection in O(nnz(A)) + n poly(k,1/eps) time.For multiple regression, TensorSketch reduces the stated time from the naive O(n2 n3) poly(k,1/eps) to O(n2+n3) poly(k,1/eps).Source: §1.3 · pp. 12–13
• Given a (1+O(eps))-approximate rank-k factorization, column, row, and tube selection achieves relative error with O(k/eps) selections each and a rank-k core; these parameter bounds are tight.Without the approximate factorization, the stated algorithmic route can require exponential time in k.Source: §1.3 · p. 12
• Given an approximate rank-k factorization, face-based CURT selects O(k/eps) row-tube, tube-column, and column-row faces and returns a rank-k tensor with relative error.The approximation assumption is that the given factorization is a (1+O(eps))-approximation to A.Source: §1.3 · p. 13
• For entrywise ℓ1 approximation, iterative flattening and dimensionality reduction yield a poly(k,log n)-approximate rank-k tensor; related results give an ℓ1 CURT with eO(k) columns, rows, and tubes and extend to 1 ≤ p < 2.The rank-k ℓ1 procedure uses Cauchy sketches and Lewis-weight sampling to reduce the problem size to poly(k), then relaxes the reduced problem to a Frobenius-norm problem.Source: §1.3 · p. 14

1.3 Other Low Rank Approximation Algorithms Following Our Framework

• For asymmetric ℓ1-ℓ2-ℓ2 and ℓ1-ℓ1-ℓ2 tensor objectives, the framework gives poly(k, log n)-approximation bicriteria solutions.The methods embed or sketch the asymmetric objectives into symmetric-norm or Frobenius-norm problems, then apply an iterative existential argument.Source: §1.3 · pp. 14–15
• With the stated assumptions on W’s distinct faces, weighted low-rank approximation admits algorithms with runtimes poly(n)·2^Õ(rk²/ε) or 2^Õ(r²k²/ε).The first assumes r distinct faces in each of three dimensions; the second assumes r distinct faces in two dimensions.Source: §1.3 · p. 15
• Under ETH, tensor rank cannot be approximated within a constant factor in 2^δk^1−o(1) time; ETH-based hardness also transfers matrix ℓ1 approximation barriers to tensor entrywise ℓ1, ℓ1-ℓ1-ℓ2, and ℓ1-ℓ2-ℓ2 approximation.The passage also states a 2^1/ε^1−o(1) hardness for tensor entrywise ℓ1 and ℓ1-ℓ1-ℓ2 approximation, and a 2^1/ε^Ω(1) hardness for tensor ℓ1-ℓ2-ℓ2 approximation.Source: §1.3 · pp. 15–16
• Under ETH, 2^Ω(1/ε^1/4) time is necessary for (1+ε)-approximation of rank-1 tensors, and 2^Ω(1/ε^1/2) time for the spectral norm of symmetric rank-1 tensors.The rank-1 approximation lower bound is established for a poly(n)-sized tensor; the same hard instance yields the spectral-norm lower bound.Source: §1.3 · pp. 15–16
• A tensor CUR hard instance requires Ω(k/ε) selected columns, rows, and tubes, and a rank-at-least-k tensor U; the construction generalizes to order q.Source: §1.3 · p. 16
• The matrix CUR runtime improves from nnz(A) log n + (n+d)·poly(log n, k, 1/ε) to nnz(A) + (n+d)·poly(k, 1/ε), while selecting the optimal numbers of rows and columns and a rank-k U.The construction uses row and column subset selection to obtain the CUR factors.Source: §1.3 · pp. 16–17
• The techniques also apply to Tucker rank and tensor train rank, which the paper identifies as alternatives to CP rank that avoid the stated best-rank-k nonexistence issue.Source: §1.3 · p. 17

1.4 Comparison to [BCV14]

• For every tensor order q, the algorithm achieves a (1+ε)-approximation in nnz(A) + n·poly(k/ε) + exp((k²/ε)·poly(q)) time, improving on [BCV14]’s O(q)-approximation.The passage attributes the improvement to adaptively choosing projection spaces across modes rather than choosing each mode’s space independently.Source: §1.4 · p. 17

B.1 Subspace Embeddings and Approximate Matrix Product

• The preliminaries define subspace embeddings and approximate matrix products, typically using a sketch to estimate A⊤B.The approximate matrix product target has Frobenius error at most ϵ∥A∥F∥B∥F.Source: §B.1 · p. 21

B.2 Tensor CURT decomposition

• Tensor CURT definitions cover exact and approximate decompositions using selected columns, rows, and tubes, as well as face-based variants; the paper contrasts its face-based approach with [TM17].The passage says [TM17] requires incoherence assumptions, has sample complexity depending on log n, and samples only two of three dimensions.Source: §B.2 · p. 23

B.3 Polynomial system verifier

• Polynomial-system verifiers determine whether a given real polynomial system has a solution, using methods of.The supplied theorem describes systems with polynomial constraints and standard relations including inequalities and equalities.Source: §B.3 · p. 25

B.4 Lower bound on the cost of a polynomial system

• For a polynomial on a compact connected component, bounds the absolute value of its minimum when that value is nonzero; bounded feasible sets let the paper apply this to a global minimum.The passage notes that bounded connected components are compact, so the theorem applies to the global minimum when the polynomial is nonzero on the set.Source: §B.4 · p. 26

B.5 Frobenius norm and ℓ2 relaxation

• The preliminaries state ℓ2-relaxation claims for ℓp regression and matrix and tensor low-rank approximation, alongside a generalized rank-constrained matrix approximation result.The listed relaxation claims concern p ∈ [1, 2).Source: §B.5 · pp. 26–27

B.6 CountSketch and Gaussian transforms

• CountSketch can be applied to a tensor, including along three dimensions, in O(nnz(A)) time.The preliminaries also define Gaussian transforms and combined CountSketch-plus-Gaussian transforms.Source: §B.6 · p. 27

B.7 Cauchy and p-stable transforms

• Sparse Cauchy and sparse p-stable transforms can each be applied to a tensor in O(nnz(A)) time.The passages also state this running time for applying three such transforms across the tensor dimensions.Source: §B.7 · pp. 28–29

B.8 Leverage scores

• Leverage-score sampling draws rows with replacement from a distribution that dominates each leverage score by a factor β and rescales the sampled rows.The sampling probabilities qi satisfy qi ≥ βpi, where pi is the corresponding leverage score.Source: §B.8 · p. 29

B.9 Lewis weights

• Lewis-weight sampling yields rescaled samples with N = O(d log d) for p = 1, O(d log d log log d) for 1 < p < 2, and O(d^(p/2) log d) for 2 ≤ p < 4.Approximate ℓp Lewis weights can be computed in O((nnz(A) + d^ω log d) log n) time; an alternative uses a well-conditioned basis and runs in n poly(d/ϵ) time.Source: §B.9 · pp. 29–30

B.10 TensorSketch

• TensorSketch sketches outer products of q possibly distinct vectors, with a subspace embedding when m ≥ k²(2 + 3q)/(ϵ²δ), succeeding with probability 1 − δ.The section states a generalized version of an earlier TensorSketch theorem that covered repeated copies of the same vector.Source: §B.10 · p. 31

C Frobenius Norm for Arbitrary Tensors

• The broader Frobenius-norm section spans tensor approximation, objective reduction, regression, bicriteria methods, subset selection, CURT, q-th-order extensions, and a matrix CUR algorithm.The overview also identifies column, row, and tube subset selection and two CURT algorithms with optimal sample complexity or running time.Source: C Frobenius Norm for Arbitrary Tensors · p. 32

C.1 (1 + ϵ)-approximate low-rank approximation

• Theorem C.1 gives a (1 + ϵ)-approximate rank-k tensor algorithm in O(nnz(A)) + n poly(k, 1/ϵ) + 2^O(k²/ϵ) time, succeeding with probability 9/10.The bit-model extension also handles cases where a rank-k optimum does not exist, given a sufficiently close bounded-norm factorization, and addresses OPT = 0 cases.Source: §C.1 · pp. 32, 33, 35

C.2 Input sparsity reduction

• Input-sparsity reduction compresses a tensor objective to dimensions poly(k, 1/ϵ) in O(nnz(A) + n poly(k/ϵ)) time while preserving the stated optimization costs.The lemma provides the guarantee with probability at least 0.99 for all eligible factor matrices.Source: §C.2 · p. 36
• Three mode-wise sparse embeddings produce a compressed tensor C = A(T1, T2, T3), computable in O(nnz(A)) time.Each TiVi can also be computed in O(nnz(Vi)) time.Source: §C.2 · pp. 37–38

C.3 Tensor multiple regression

• TensorSketch with s = O(k^2 + k/ϵ) yields a (1+ϵ)-approximation for tensor multiple regression in O(nnz(A) + nnz(U) + nnz(V) + d poly(k, 1/ϵ)) time.The sketch has one nonzero per row, allowing the sketched input to be computed in O(nnz(A)) time.Source: §C.3 · pp. 38–39

C.4.1 Solving a small regression problem

• A structured solver computes α′ for three-factor tensor regression in O(nnz(A) + n poly(s1, s2, s3, 1/ϵ)) time, with probability at least .99.The approach improves on explicitly forming an n^3-dimensional linear regression; a related sparse-embedding lemma uses t1 = poly(r1/ϵ) and t2 = poly(r2/ϵ) for a uniform-in-X guarantee with probability at least 0.99.Source: §C.4.1 · pp. 39–40

C.4.2 Algorithm I

• Algorithm I first presents a cubic-rank variant, with r = O(k³/ϵ³) and running time O(nnz(A) + n poly(k, 1/ϵ)).The optimized quadratic-rank version is presented afterward.Source: §C.4.2 · pp. 41–42
• Algorithm I sketches flattened tensor modes, combines the sketched factors, and uses regression to construct the remaining factor without explicitly writing down a large intermediate matrix.The intermediate matrix would require Ω(n²) time to write down; TensorSketch is used for the regression step.Source: §C.4.2 · pp. 41, 42, 44
• The optimized Algorithm I uses rank O(k²/ϵ²) and runs in O(nnz(A) + n · poly(k, 1/ϵ)) time for third-order tensors.Theorem C.8 states success probability 9/10.Source: §C.4.2 · p. 42
• With probability at least 9/10, Algorithm I runs in nnz(A) + n · poly(k/ϵ) time and returns rank O(k²/ϵ²), with error at most (1 + ϵ) OPT + γ when the best rank-k tensor may not exist.Here γ is an arbitrarily small positive function of n.Source: §C.4.2 · p. 45

C.4.4 Algorithm II

• Algorithm II uses Gaussian sketches on tensor flattenings and reports an error bound of (1 + ϵ)α² OPT for its rank-k² construction, with success probability 9/10.The described regression sketching reduces the intermediate problems before constructing the approximation.Source: §C.4.4 · pp. 47–48

C.5 Generalized matrix row subset selection

• O(nnz(A) log n)+(m+n) poly(k,1/ϵ) time outputs a diagonal rescaling with O(k/ϵ) nonzeros, equivalently that many rescaled rows.The theorem also outputs U; the supplied passage does not include the approximation guarantee that follows.Source: §C.5 · p. 48
• The selected rows form R=DA for a diagonal matrix D with O(k/ϵ) nonzeros.The procedure also uses a sparse subspace embedding and row sampling to construct its rank-k output.Source: §C.5 · p. 49
• O(nnz(A))+(m+n) poly(k,1/ϵ) time suffices when min(m,n)=poly(k,1/ϵ), outputting O(k/ϵ) rescaled rows and a matrix U.The stated success probability is .99.Source: §C.5 · p. 49
• The faster small-dimension variant removes the log n factor by using CountSketch with poly(k,1/ϵ) rows instead of Gaussian sketching.With that sketch size, the additional matrix S is no longer needed.Source: §C.5 · p. 49

C.6 Column, row, and tube subset selection, (1 + ϵ)-approximation

• Theorem C.20 is a warm-up that returns column, row, and tube subsets of size poly(k, 1/ϵ) in O(nnz(A)) + n poly(k, 1/ϵ) time, while guaranteeing only that a rank-poly(k/ϵ) core tensor exists.It does not output the core tensor; the faster algorithm has slightly worse sample complexity by polylogarithmic factors.Source: §C.6 · pp. 52–53
• Theorem C.21 runs in O(nnz(A) + n poly(k, 1/ϵ)) time and returns column, row, and tube subsets plus a core tensor U of rank poly(k, 1/ϵ), with the guarantee holding with probability 9/10.The subset sizes are also poly(k, 1/ϵ).Source: §C.6 · p. 54

C.7.1 Properties of leverage score sampling and BSS sampling

• Using ideas from [BW14] and [CEM+15], the algorithm reduces the number of nonzero entries from O(ϵ−2k log k) to O(ϵ−2k) and improves the running time to input sparsity.Source: §C.7.1 · p. 55

C.7.2 Row sampling for linear regression

• For linear regression, sampling and rescaling with O(k) rows gives a (1±1/2) subspace embedding, while O(k/ϵ) rows suffice for a √ϵ-operator-norm approximate matrix product.Source: §C.7.2 · p. 56

C.7.3 Leverage scores for multiple regression

• For multiple regression, leverage-score sampling with O(d log d) rows gives a (1±1/2) subspace embedding, while O(d/ϵ) rows yield an ϵ/d-Frobenius-norm approximate matrix product.Source: §C.7.3 · p. 57

C.7.4 Sampling columns according to leverage scores implicitly, improving polynomial running time to nearly linear running time

• For U, V ∈ R^(k×n), implicit leverage-score sampling of columns of U ⊙ V improves the running time from Ω(n²) to O(n poly(log n, k, 1/ϵ)); for general q-th order tensors, the polylog factor is removed.The method samples without explicitly writing down the n² leverage scores.Source: §C.7.4 · p. 59
• The sampler draws an index i, then j2, then j1, using Gaussian sketches to estimate intermediate norms before selecting the final coordinate.The final j1 probabilities are computed from |(U′i⊤)j1Vj2|2 in O(n1k) time.Source: §C.7.4 · pp. 60–61
• O((n1 + n2) · poly(log(n1n2), k, 1/ϵ)) time suffices to approximate leverage-score sampling probabilities for tensor-product columns.The algorithm uses sequential sampling and sketch-based estimates of intermediate norms.Source: §C.7.4 · p. 61
• For A, V, W ∈ R^(k×n), an algorithm runs in O(n · poly(k, 1/ϵ)) time and outputs a diagonal D with O(k log k + k/ϵ) nonzeros.The lemma states its guarantee holds with probability at least 0.999.Source: §C.7.4 · p. 62
• Replacing Theorem C.46 with Lemma C.32 yields a variant running in n poly(log n, k, 1/ϵ) time with better dependence on k.Source: §C.7.4 · p. 62

C.7.5 Input sparsity time algorithm

• The algorithm takes as input three matrices that provide a rank-k, α-approximation to the third-order tensor.The output comprises C, R, T, and U.Source: §C.7.5 · pp. 62–63
• O(nnz(A)+n poly(k,1/ϵ)) time outputs columns, rows, and tubes from A, with a rank-k tensor U.Each subset has size O(k log k+k/ϵ).Source: §C.7.5 · pp. 62, 64
• The three factor estimates use leverage-score samples of paired-factor products, with sample counts d1=d2=d3=O(k log k+k/ϵ) for the three modes.Source: §C.7.5 · pp. 63–64

C.7.6 Optimal sample complexity algorithm

• With probability 9/10, the optimal-sample-complexity CURT algorithm selects O(k/ϵ) columns, rows, and tubes per mode and runs in O(nnz(A) log n + n^2 poly(log n, k, 1/ϵ)) time.The output includes a rank-k tensor U.Source: §C.7.6 · p. 64

C.8 Face-based selection and decomposition

• The face-based CURT variants select column-row, row-tube, and column-tube faces; the second starts from a rank-k (1+O(ϵ))-approximation and outputs U.The first is a polynomial-time bicriteria algorithm, while the second outputs U but the first does not.Source: §C.8 · p. 65

C.8.1 Column-row, column-tube, row-tube face subset selection

• Face subset selection returns row-tube, column-tube, and column-row faces, with poly(k, 1/ϵ) samples and a corresponding tensor U.The stated runtime is O(nnz(A) log n + n^2 poly(log n, k, 1/ϵ)).Source: §C.8.1 · pp. 65, 68

C.8.2 CURT decomposition

• Given a rank-k α-approximation, face-based CURT returns rank-k U and O(k/ϵ) faces per mode in O(nnz(A) log n + n^2 poly(log n, k, 1/ϵ)) time.Its error is at most (1+ϵ)^3 α OPT with probability 9/10.Source: §C.8.2 · pp. 68–70

C.9 Solving small problems

• The small-problem solver outputs three fitted matrices in n^O(δ)·2^O(d1k+d2k+d3k) time.It takes a tensor and three matrices as input.Source: §C.9 · p. 70

C.10 Extension to general q-th order tensors

• For general q-th order tensors, the analysis hides q-dependent factors using O_q(·), reflecting that q is constant in most practical applications.Source: §C.10 · p. 71

C.10.1 Fast sampling of columns according to leverage scores, implicitly

• Implicit leverage-score sampling for a q-way column product runs in O_q(n · poly(k, 1/ϵ) · R_samples) time, without explicitly forming the product.The resulting sampling procedure also supports a diagonal sampling-and-rescaling matrix with O(k log k + k/ϵ) nonzeros and a relative-error guarantee with probability at least 0.999.Source: §C.10.1 · pp. 71, 73

C.10.2 General iterative existential proof

• The iterative existential proof fixes approximations one mode at a time, using Gaussian sketches of size O(k/ϵ) in each round.At each round it holds earlier approximations fixed and uses the remaining optimal factors; the stated sketch sizes are O_q(k/ϵ′).Source: §C.10.2 · pp. 74–75

C.10.3 General input sparsity reduction

• General input sparsity reduction sketches each factor matrix and the tensor along its modes, with success probability 99/100 and sketch dimensions t_i = O_q(poly(b_i, 1/ϵ)).The setup assumes each V_i has b_i ≤ poly(k, 1/ϵ) columns.Source: §C.10.3 · p. 75

C.10.4 Bicriteria algorithm

• For a q-th order tensor, the bicriteria algorithm returns a rank-r approximation with r = O_q((k/ϵ)^(q−1)) in O_q(nnz(A) + n · poly(k, 1/ϵ)) time.Source: §C.10.4 · p. 75

C.10.5 CURT decomposition

• The general q-th order CURT method iteratively applies its tensor selection proof across q modes, selecting d_i columns per mode and constructing a core tensor U.Each mode uses either d_i = O_q(k log k + k/ϵ) or d_i = O_q(k/ϵ) selected columns.Source: §C.10.5 · p. 76

C.11 Matrix CUR decomposition

• The paper presents the first matrix CUR algorithm running in nnz(A) time, improving on the previous best Frobenius-norm algorithm [BW14].Source: §C.11 · p. 77

C.11.1 Algorithm

• The matrix CUR algorithm runs in O(nnz(A) + n · poly(k, 1/ϵ)) time and returns rank-k U with r = c = O(k/ϵ) rows and columns, respectively, with probability at least 9/10.C contains columns from A, R contains rows from A, and U has dimensions c × r.Source: §C.11.1 · p. 77
• The CUR construction uses O(k/ϵ) reweighted columns and rows of A.The sampled columns and rows form a CUR decomposition of A.Source: §C.11.1 · p. 79

C.11.2 Stronger property achieved by leverage scores

• With O(ϵ^-2 k log(k)) nonzero entries, leverage-score sampling satisfies the stated embedding and approximate-product conditions with probability at least 0.99.The conditions are a (1 + ϵ)-subspace embedding for A and an (ϵ/k)-Frobenius norm approximate matrix product for A.Source: §C.11.2 · p. 79

D Entry-wise ℓ1 Norm for Arbitrary Tensors

• The tensor ℓ1 section introduces methods for entry-wise low-rank approximation, including bicriteria algorithms and ℓ1-norm CURT decomposition.Its roadmap also includes existence results, objective-size reduction, and algorithms for small problem sizes.Source: D Entry-wise ℓ1 Norm for Arbitrary… · p. 83

D.1 Facts

• The section presents a method to reduce an entry-wise ℓ1 objective to a Frobenius-norm objective.Fact D.1 gives a tensor approximation relation involving a factor of √(c1c2c3) for the ℓ1 bound.Source: §D.1 · p. 83

D.2 Existence results

• For a 3rd-order tensor, three sketching options achieve the stated guarantee with probability 99/100, with different sketch sizes and approximation factors.Dense Cauchy transforms use s1 = s2 = s3 = eO(k), α = eO(k^1.5) log^3 n; sparse Cauchy transforms use s1 = s2 = s3 = eO(k^5), α = eO(k^13.5) log^3 n; guessing Lewis weights uses s1 = s2 = s3 = eO(k), α = eO(k^1.5).Source: §D.2 · p. 84

D.3 Polynomial in k size reduction

• Under the stated dilation, contraction, and sketch-fit conditions, the unsketched ℓ1 tensor fit is ≲β1β2β times the optimum.The result transfers the sketched fit guarantee to the original tensor objective.Source: §D.3 · p. 87
• Lewis-weight sampling yields a polynomial-size reduced objective and a tensor approximation algorithm running in O(nnz(A)) + n poly(b1, b2, b3) time.The reduction outputs a tensor and three matrices with c1 = c2 = c3 = poly(b1, b2, b3), with probability 0.99.Source: §D.3 · pp. 88–89

D.4 Solving small problems

• When a feasible solution has entries expressible using O(n^δ) bits, an n^O(δ) · 2^O(d1k+d2k+d3k)-time algorithm outputs matrices attaining OPT.The algorithm solves the small tensor problem exactly under the stated bit-length condition.Source: §D.4 · p. 91

D.5 Bicriteria algorithms

• The bicriteria results trade rank against runtime, progressing from nearly input-sparsity time to input-sparsity time and then reducing cubic rank to quadratic rank.Theorems D.12–D.15 provide the stated tradeoffs.Source: §D.5 · p. 92

D.5.1 Input sparsity time

• Theorem D.12 uses rank eO(k^3) with nearly input-sparsity time, while Theorem D.13 uses rank eO(k^15) with input-sparsity time.Their stated runtimes are nnz(A)·eO(k)+O(n)poly(k)+poly(k) and nnz(A)+O(n)poly(k)+poly(k), respectively.Source: §D.5.1 · p. 93

D.5.2 Improving cubic rank to quadratic rank

• For any third-order tensor A, k ≥ 1, and ϵ ∈ (0, 1), Theorem D.14 outputs three n×r matrices with r = eO(k²) in nnz(A)·eO(k)+O(n)poly(k)+poly(k) time.Under the same conditions, Theorem D.15 outputs three n×r matrices with r = eO(k¹⁰) in nnz(A)+O(n)poly(k)+poly(k) time.Source: §D.5.2 · pp. 94–95

D.6 Algorithms

• The section introduces two algorithms using different sketches: Theorem D.17 prioritizes fast runtime, while Theorem D.19 gives the best approximation ratio.Source: §D.6 · p. 96

D.6.1 Input sparsity time algorithm

• Theorem D.17 achieves an ℓ1 error bound of poly(k, log n) times rank-k OPT in nnz(A)·eO(k)+O(n)poly(k)+2^eO(k^2) time; Corollary D.18 reduces the runtime to nnz(A)+O(n)poly(k)+2^eO(k^2).Both results output rank-k factors and hold with probability at least 9/10.Source: §D.6.1 · pp. 96, 98

D.6.2 eO(k3/2)-approximation algorithm

• The provided D.6.2 excerpt specifies guessing diagonal sketches and applying polynomial-k size reduction, but does not include the theorem guarantee.Source: §D.6.2 · p. 98
• With probability at least 9/10, the algorithm outputs U, V, W ∈ R^(n×k) with ℓ1 error at most ~O(k^(3/2)) times the best rank-k error, in n^{~O(k)}2^{~O(k^3)} time.The bound is ∥U ⊗ V ⊗ W − A∥1 ≤ ~O(k^(3/2)) min_rank-k A′ ∥A′ − A∥1.Source: §D.6.2 · p. 98

D.7 CURT decomposition

• Given a rank-k, α-approximation, CURT outputs column, row, and tube subsets of size O(k log k), a rank-k core, and runs in O(nnz(A)) + O(n^2) poly(k) time.The combined construction additionally runs in O(nnz(A)) + O(n^2) poly(k) + 2^{~O(k^2)} time and succeeds with probability 9/10.Source: §D.7 · pp. 98, 101

E Entry-wise ℓp Norm for Arbitrary Tensors, 1 < p < 2

• The next section presents entry-wise ℓp low-rank algorithms for arbitrary tensors when 1 < p < 2, including existence results, objective-size reduction, bicriteria methods, and CURT decomposition.It notes that if a rank-k solution does not exist, the bicriteria and rank-k algorithms can be stated in the forms of Theorems 1.1 and 1.2, respectively.Source: E Entry-wise ℓp Norm for Arbitrary… · p. 102

• The sketching guarantee holds with probability at least 0.999.Source: §E.1 · p. 102
• The proof constructs bU=AS(VS)† and uses ℓp/ℓ2 norm inequalities to transfer the sketch property into the bound.Source: §E.1 · pp. 102–103
• Dense p-stable sketches use s=e^O(k), α=e^O(k^(1−p/2))log d; sparse p-stable sketches use s=e^O(k^5), α=e^O(k^(5−5p/2+2/p))log d.Source: §E.1 · p. 103
• Lewis-weight sampling uses s=e^O(k) and α=e^O(k^(1−p/2)).Source: §E.1 · pp. 102–103

E.2 Existence results

• Theorem E.2 establishes existence of three sketching matrices with probability 99/100, with stated dimension and approximation-factor tradeoffs across three sketch choices.Dense p-stable transforms use s1 = s2 = s3 = eO(k) and α = eO(k^(3−1.5p)) log^3 n; sparse p-stable transforms use eO(k^5) dimensions and α = eO(k^(15−7.5p+6/p)) log^3 n; guessing Lewis weights uses eO(k) dimensions and α = eO(k^(3−1.5p)).Source: §E.2 · p. 103

E.3 Polynomial in k size reduction

• Lemma E.6 reduces the problem to a tensor and matrices of size polynomial in the input basis widths, preserving an α-factor comparison with probability 0.99.It runs in O(nnz(A)) + n poly(b1, b2, b3) time when min(b1, b2, b3) ≥ k; Theorem E.5 also gives a contraction-based reduction guarantee.Source: §E.3 · pp. 106–107

E.4 Solving small problems

• For p = a/b with integer a and b, combining Section B.5 in [SWZ17] with Theorem D.4 yields the ℓp version of Theorem D.4.Source: §E.4 · p. 108

E.5 Bicriteria algorithm

• The bicriteria algorithms trade rank and runtime: Theorem E.7 uses rank eO(k^3), E.8 rank eO(k^15), and E.9 rank eO(k^2).The E.7 and E.9 runtimes are nnz(A) · eO(k) + n poly(k) + poly(k); E.8 takes nnz(A) + n poly(k) + poly(k). Combining sparse and dense p-stable transforms yields nnz(A)-time at the cost of additional poly(k) approximation factors.Source: §E.5 · pp. 108–109

E.6 Algorithms

• Theorem E.11 gives a rank-k algorithm in O(nnz(A)) + n poly(k) + 2 eO(k^2) time, while E.12 gives a rank-k algorithm with runtime n eO(k)^2 eO(k^3).The section characterizes E.11 as fast-running and E.12 as having the best approximation ratio; both guarantees hold with probability at least 9/10.Source: §E.6 · p. 110

E.7 CURT decomposition

• Given a rank-k α-approximation, Theorem E.13 constructs a CURT decomposition in O(nnz(A)) + O(n^2) poly(k) time, with c = r = t = O(k log k log log k).Its output selects columns, rows, and tubes from A and has a rank-k core tensor U.Source: §E.7 · p. 110

F.2 ℓ1-Frobenius (a.k.a ℓ1-ℓ2-ℓ2) norm

• M-estimator tensor approximation is harder because flattening along any dimension can change the loss, unlike for Frobenius or entrywise ℓ1 norms.The discussion covers ℓ1-ℓ2-ℓ2 and ℓ1-ℓ1-ℓ2 settings.Source: Robust Subspace Approximation… · p. 113

F.1 Preliminaries

• The preliminaries define nice M-estimators by symmetry, vanishing at zero, and monotonicity in absolute value, and identify M2 and Lp subclasses.M2 uses p = 2; Lp consists of M(x) = |x|^p for p ∈ [1, 2).Source: §F.1 · p. 113

F.2.1 Definitions

• The section defines v-norms for tensors and matrices, along with a sampling-and-rescaling version for estimating a matrix v-norm.It also introduces an entrywise row-weighted matrix variant.Source: §F.2.1 · pp. 113–114

F.2.2 Sampling and rescaling sketches

• Sampling-and-rescaling sketches provide norm guarantees for rank-z matrix candidates, with sketch size and failure probability controlled by the stated parameters.The section presents both lower/upper threshold guarantees and a sampling-size bound for such sketches.Source: §F.2.2 · p. 114

F.2.3 No dilation and no contraction

• For fixed U* and an optimal rank-k V*, sampling and rescaling with poly(k) nonzero entries gives high-probability no-dilation and no-contraction guarantees over rank-k alternatives.The stated success probability is at least .99 for each guarantee.Source: §F.2.3 · p. 116

F.2.4 Oblivious sketches, MSketch

• An MSketch applied to a tensor can be computed in O(nnz(A)) time, and poly(k, log n)-row MSketches support no-dilation and no-contraction guarantees.The guarantee passages state success probability at least .99.Source: §F.2.4 · pp. 117–118

F.2.5 Running time analysis

• The CountSketch-composed tensor transforms (SA)iSi and Ti(SA)iSi can each be computed in O(nnz(A)) time for i ∈ {2, 3}.The proof uses the fact that each nonzero tensor entry affects only one output entry in the corresponding computation.Source: §F.2.5 · pp. 118–119

F.2.6 Algorithms

• The improved method replaces sampling-and-rescaling guesses with an oblivious sketch, then applies input-sparsity reduction to shrink the objective before solving the regression problem.CountSketch transforms are used for the reduction; the earlier warm-up does not need this step because its running time is dominated by guessing.Source: §F.2.6 · pp. 119, 125
• The warm-up sampling-and-rescaling algorithm gives a poly(k)-approximation in n^poly(k) time, with r=O(k^2) and success probability at least 9/10.The algorithm selects the best solution over its guesses; the number of guesses dominates its running time.Source: §F.2.6 · pp. 119, 120, 123
• The oblivious-sketch algorithm achieves a poly(k, log n)-approximation in O(nnz(A)) + n poly(k, log n) time, with r=O(k^2) and success probability at least 9/10.It outputs three matrices U, V, W; the sketch uses an oblivious MSketch and CountSketch input-sparsity reduction.Source: §F.2.6 · pp. 123–125

F.3.1 Definitions

• For p = 1, the u-norm satisfies the triangle inequality for both matrices and tensors, and p is a parameter associated with the nice M-estimator M().Source: §F.3.1 · pp. 126–127

F.3.2 Projection via Gaussians

• A rescaled Gaussian matrix with k = O(n/ϵ^2) rows is used to establish a high-probability guarantee that holds for all vectors in R^n.The stated success probability is at least 1 − 2^-Ω(n/ϵ^2).Source: §F.3.2 · p. 128

F.3.3 Reduction, projection to high dimension

• With probability at least 1 − 2^-Ω(n/ϵ^2), a Gaussian matrix with O(n/ϵ^2) columns preserves the tensor u-norm approximation error within factors 1 − ϵ and 1 + ϵ after projection to an ℓ1 error.The guarantee holds simultaneously for all U, V, W ∈ R^{n×k} and uses a third-order tensor A ∈ R^{n×n×n}.Source: §F.3.3 · p. 129

F.3.4 Existence results

• Three sketch matrices exist with probability 99/100; dense, sparse, and Lewis-weight variants have different sketch sizes and approximation factors.The dense and Lewis-weight variants use s1=s2=s3=eO(k), while the sparse variant uses eO(k^5); their stated α factors differ as well.Source: §F.3.4 · p. 130

F.3.5 Running time analysis

• Sparse Cauchy or Lewis-weight sketches reduce the stated computation costs to O(nnz(A)d); other choices add sketch-dependent terms.The added terms are ns1t1, ns2t2, or ds3t3, depending on the flattened dimension.Source: §F.3.5 · p. 132

F.3.6 Algorithms

• For an n×n×n tensor A and k≥1, the algorithm outputs U,V,W∈R^(n×k) in O(nnz(A)n)+eO(n)poly(k)+n²eO(k²) time, with u-norm error at most poly(k, log n) times the best rank-k error, with probability at least 9/10.Source: §F.3.6 · p. 133
• Other algorithms include a rank-k solver using direct entrywise ℓ1 optimization and a bicriteria solver with r=eO(k^2) and O(nnz(A)n)+eO(n)poly(k) running time.The stated probability for these results is at least 9/10.Source: §F.3.6 · p. 134

G Weighted Frobenius Norm for Arbitrary Tensors

• The weighted-tensor section combines new tensor techniques with existing weighted low-rank algorithms and covers weights with distinct faces or columns and rows.It also notes a simpler presented version assumes an optimal rank-k tensor exists and its factors have bounded norms.Source: G Weighted Frobenius Norm for… · p. 135

G.1 Definitions and Facts

• G.1 defines weighted Frobenius norms for matrices and tensors and introduces Cramer’s rule as a key tool.Source: §G.1 · pp. 135–136

G.2 r distinct faces in each dimension

• For weights with r distinct faces in each dimension, Theorem G.2 gives a weighted rank-k algorithm under stated existence and input-size assumptions, running in (nnz(A)+nnz(W)+n^2eO(rk^2/ϵ))n^O(δ) time with probability 9/10.The theorem assumes OPT>0 and an existing rank-k tensor; the weight entries are represented using O(n^δ) bits.Source: §G.2 · p. 136
• A Gaussian sketch with s1 = O(k/ε) yields a solution whose objective is at most (1 + ε) OPT.The proof encodes the construction using O(rk^2/ε) variables, polynomial degree poly(kr), and O(1) constraints.Source: §G.2 · pp. 137–138

G.3 r distinct columns, rows and tubes

• If W has r distinct columns and rows, it has at most r distinct column-tube faces and at most r distinct row-tube faces.With r distinct columns, rows, and tubes, W has r distinct faces in each of the three orientations, so Theorem G.2 also applies under this assumption.Source: §G.3 · pp. 140–142

G.4 r distinct columns and rows

• For weights with r distinct faces in two dimensions, Theorem G.5 gives a weighted rank-k approximation algorithm running in (nnz(A) + nnz(W) + n^2·2^{O(r^2k^2/ϵ)})n^{O(δ)} time and succeeding with probability at least 9/10.The theorem covers several cases involving whether OPT is zero and whether an optimal rank-k tensor exists; its inputs have entries representable using O(n^δ) bits.Source: §G.2 · p. 136, §G.4 · pp. 142–143
• With r distinct columns and rows, a tensor has at most 2^{O(r log r)} distinct column-row faces, and an example has 2^{Ω(r log r)} such faces.The upper bound is therefore matched in its exponent by the example described in the section.Source: §G.4 · pp. 144–145

H Hardness

• Appendix H covers hardness for tensor eigenvalue, singular-value, spectral-norm, rank-1 approximation, tensor rank, and robust subspace approximation problems.It also notes hardness results implied by matrix hardness results.Source: H Hardness · p. 146

H.1 Definitions

• Under ETH, MAX-E3SAT has no 2^{o(n^{1-o(1)})}-time algorithm distinguishing satisfiable instances from those with at most a 7/8 + δ satisfiable fraction.ETH asserts that 3SAT cannot be solved in O(2^{δn}) time for some δ > 0.Source: §H.1 · p. 146

H.2 Symmetric tensor eigenvalue

• Unless ETH fails, approximating the largest eigenvalue of an n-dimensional symmetric tensor within (1 ± Θ(1/n)) requires 2^{Ω(√n)} time; padding also rules out polynomial-time approximation within 1 ± Θ(1/log^{2+γ}(n)).The eigenvalue lower bound follows from a reduction from computing the stability number of a graph.Source: §H.2 · p. 148

H.3 Symmetric tensor singular value, spectral norm and rank-1 approximation

• The section defines tensor ℓ2 singular values and spectral norm, and states that the spectral norm is the maximum ℓ2 singular value.It considers one of the two kinds of tensor singular values defined in [HL13].Source: §H.3 · pp. 148–149
• Unless ETH fails, spectral norm approximation has no 2^{o(sqrt n)}-time algorithm within (1 + Θ(1/n)) relative error, or polynomial-time algorithm within (1+Θ(1/log^{2+γ(n)})) relative error.The polynomial-time lower bound also applies to approximating the largest singular value within (1 + Θ(1/ log2+γ(n))) relative error, for arbitrarily small constant γ > 0.Source: §H.3 · p. 149
• Unless ETH fails, no polynomial-time algorithm approximates the best rank-1 tensor approximation within (1 + Θ(1/ log2+γ(n))) relative error, for arbitrarily small constant γ > 0.Source: §H.3 · p. 150

H.4 Tensor rank is hard to approximate

• The paper strengthens Håstad’s NP-hardness result [Hås90] by showing that approximating tensor rank is hard, not only deciding tensor rank.Source: §H.4 · p. 150

H.4.1 Cover number

• If a MAX-E3SAT(B) instance is at most 7/8 + A satisfiable, its cover number is at least (1/8 − A)m/B.The cover number counts the minimum number of variables assigned ∗ so that all clauses become true.Source: §H.4.1 · pp. 151–152

H.4.2 Properties of 3SAT instances

• For 3SAT instances with m = Θ(n) and satisfiability (1−c)m, the number of variables in a minimum-unsatisfied-clause set is between Ω((cm)^{1/3}) and O(cm).Source: §H.4.2 · p. 152
• With probability 1−2^{-Ω(log n log log n)}, random 3SAT instances have no literal in at least log n clauses; under the stated conditions, each literal appears O(log n) times among unsatisfied clauses.For sufficiently large constant c and m = cn, with probability at least 1−9m^{−Bbn}, at least (1−b)m clauses have variables appearing in at most B clauses within that subset.Source: §H.4.2 · pp. 152–153

H.4.3 Reduction

• The reduction constructs a tensor whose rank is at most 4n + 2m for satisfiable formulas, and between 4n + 2m + Ω(p) and 4n + 2m + O(p) when an unsatisfiable formula has cover number p.The constructed tensor has dimensions n1 = 2 + n + 2m, n2 = 3n, and n3 = 3n + m.Source: §H.4.3 · pp. 154, 156
• For a 3SAT instance S with cover number p, the constructed tensor T has rank at most 4n + 2m + p.Source: §H.4.3 · p. 158
• The decomposition gives rank(T2) = n + 2m, while T1 has rank at least 3n + |P| for P indexing nonzero second rows of fMi.T2’s rank follows from n rank-1 and m rank-2 separated subtensors.Source: §H.4.3 · pp. 158–159
• For an unsatisfiable 3SAT instance with cover number p, the constructed tensor has rank at least 4n + 2m + Ω(p).The proof combines lower bounds 4n + 2m + Ω(p) − q and 4n + 2m + q.Source: §H.4.3 · p. 163
• Unless ETH fails, no 2^{δk^{1−o(1)}}-time algorithm distinguishes tensor rank at most k from rank at least c0k for q-th order tensors with q ≥ 3.The reduction proceeds through MAX-3SAT to MAX-E3SAT and then to bounded-occurrence MAX-E3SAT.Source: §H.4.3 · p. 163
• Under random-ETH, deciding whether a q-th order tensor has rank at most k or at least c0k requires 2^Omega(k) time for some absolute constant c0 > 1.The theorem states this lower bound for deterministic algorithms.Source: §H.4.3 · p. 163
• If BPP = P, the same lower bound applies to randomized algorithms that succeed with probability 2/3.The argument pads an n × n × n tensor with zeros to dimensions 2^g(n) × 2^g(n) × 2^g(n), where g(n) = o(n), so a randomized algorithm running in 2^(c g(n)) time for c > 3 would be polynomial in the padded input size while the deterministic lower bound remains 2^Omega(n).Source: §H.4.3 · p. 164

H.5 Hardness result for robust subspace approximation

• Robust subspace approximation is NP-hard within a 1+1/poly(d) factor and, unless ETH fails, cannot be approximated within 1+1/poly(log d), improving the prior 1±1/poly(d) hardness.The ETH-based reduction pads the constructed instance to obtain a point set with a polylogarithmic-dimension approximation gap.Source: §H.5 · pp. 164, 166, 167

H.6 Extending hardness from matrices to tensors

• The tensor hardness strategy embeds a hard matrix as one tensor face and zeros elsewhere, so an optimal tensor solution recovers an optimal matrix solution.This extends matrix hardness to tensor problems, including entry-wise ℓ1 and asymmetric ℓ1-ℓ1-ℓ2 approximation.Source: §H.6 · p. 167, §H.6.1 · p. 168

H.6.1 Entry-wise ℓ1 norm and ℓ1-ℓ1-ℓ2 norm

• Under ETH, rank-1 tensor approximation in entry-wise ℓ1 and ℓu norms has no (1+epsilon)-approximation algorithm running in 2^O(1/epsilon^(1−gamma)) time.The section also derives hardness for entry-wise ℓ1 and asymmetric ℓ1-ℓ1-ℓ2 tensor approximation from matrix hardness.Source: §H.6.1 · pp. 168–169

H.6.2 ℓ1-ℓ2-ℓ2 norm

• Unless ETH fails, for arbitrarily small constant γ > 0, no poly(n)-time algorithm computes bU, bV, cW ∈ R^(n×k) for some A ∈ R^(n×n×n) with the stated 1 + 1/poly(log n) guarantee.Source: §H.6.2 · p. 169

I.1 Frobenius CURT decomposition for 3rd order tensor

• For third-order tensors, relative-error Frobenius CURT decomposition can require Ω(k/epsilon) columns, rows, and tubes, and a core U of rank Ω(k).The section introduces hard instances for tensor problems and establishes this CURT lower bound for a constructed tensor.Source: §I.1 · p. 171, I Hard Instance · p. 171
• The argument concludes by contradiction that CURT with o(k/ϵ) columns, rows, or tubes cannot attain (1+ϵ) relative Frobenius error, using symmetry across tensor directions.The passage frames the cost lower bound for selecting few columns or rows and then states that the resulting argument gives a contradiction.Source: §I.1 · pp. 172–173

I.2 General Frobenius CURT decomposition for q-th order tensor

• Theorem I.2 forces c_i = Ω(k/ε) columns in every dimension and rank(U) ≥ c′k for its stated CURT condition.The theorem applies for any constant q, any k ≥ 1, and ε < c′, where c′ < 1 is a constant.Source: §I.2 · p. 173
• The hard q-th order tensor is constructed by repeating a matrix built from D and arranging copies of B and B⊤ across dimensions.The construction is symmetric across tensor directions; for even q it uses q/2 copies of each orientation, with a corresponding split for odd q.Source: §I.2 · p. 174
• The proof derives a contradiction from an approximation ratio greater than 1 + ε and concludes that the rank is at least Ω(k).The cited proof passage specifies the inequality when b > 3.Source: §I.2 · p. 175

J Distributed Setting

• In the arbitrary-partition model, each of s machines holds a local tensor, their sum is implicit, and communication passes through a coordinator.The total communication cost counts words exchanged with the coordinator; each word has O(log(sn)) bits.Source: J Distributed Setting · p. 176
• Theorem J.3 gives a constant-success protocol with communication complexity s(poly(k/ε) + O(kn)) words.The protocol solves the distributed Frobenius norm rank-k tensor approximation problem in the arbitrary-partition model.Source: J Distributed Setting · pp. 176–177
• If each machine keeps its own factor matrix instead of sending the factors to the coordinator, communication falls to at most s·poly(k/ε) words.This is the setting described in Remark J.4.Source: J Distributed Setting · p. 177
• Algorithm 39 requires exponential-in-poly(k/ε) time for its line-23 solver, while the replacement regression problem computes α* in polynomial time.The remark identifies the regression formulation as an alternative to solving line 23.Source: J Distributed Setting · p. 177
• With Cauchy sketching matrices, the protocol also handles distributed entry-wise ℓ1 rank-k approximation, retaining the same communication bound.A bicriteria solution in this variant requires only polynomial running time.Source: J Distributed Setting · pp. 178–179

K Streaming Setting

• The turnstile-streaming algorithm solves Frobenius-norm rank-k tensor approximation with constant success probability using poly(k/ϵ) + O(nk/ϵ) words.It uses one pass over the update stream and outputs three n × k matrices.Source: K Streaming Setting · p. 180

L Extension to Other Tensor Ranks

• The framework extends beyond CP rank to Tucker rank and tensor train rank.The Tucker-rank definition represents a third-order tensor using three n × k matrices and a k × k × k core.Source: L Extension to Other Tensor Ranks · p. 184, §L.1.1 · p. 184

L.1.1 Definitions

• Tucker rank is the smallest k for which a third-order tensor can be represented by three n × k matrices and a k × k × k core.Source: §L.1.1 · p. 184

L.1.2 Algorithm

• The Tucker-rank approximation algorithm runs in O(nnz(A)) + n poly(k, 1/ϵ) + 2^O(k^2/ϵ+k^3) time and outputs three n × k matrices and a k × k × k core.Its staged optimization objectives have costs at most (1 + ϵ) OPT and (1 + ϵ)^2 OPT.Source: §L.1.2 · pp. 184–186

L.2.1 Definitions

• Tensor train rank k is defined through a third-order factorization with tensors of shapes 1 × n × k, k × n × k, and k × n × 1.Source: §L.2.1 · p. 187

L.2.2 Algorithm

• The tensor train-rank algorithm runs in O(nnz(A)) + n poly(k, 1/ϵ) + 2^O(k^4/ϵ) time and outputs tensors of shapes 1 × n × k, k × n × k, and k × n × 1.The supplied theorem passage gives the algorithm's runtime and output shapes but does not include its approximation guarantee.Source: §L.2.2 · p. 187
• The second optimization step has cost at most (1 + ϵ) OPT and uses a sketch with s2 = O(k^2/ϵ).Its optimal solution is bV = A2S2(Z2S2)†.Source: §L.2.2 · p. 189
• After fixing bU and bV, the third optimization step has cost at most (1 + ϵ)^2 OPT and sketches with s3 = O(k/ϵ).The optimal solution is cW = A3S3(Z3S3)†.Source: §L.2.2 · pp. 189–190
• The algorithm combines the three sketched matrices using Lemma C.3, then applies Theorem C.45; correctness follows by rescaling ϵ by a constant factor.The stated running time is nnz(A) + n poly(k, 1/ϵ) plus 2^O(k^4/ϵ), ignoring bit complexity.Source: §L.2.2 · p. 190