Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

1.1 Main Results

• The paper resolves the open target of solving dense k-well-conditioned systems in near-optimal time, while extending the guarantee to suitably averaged conditioning.The motivating lower bound is Ω(d^2 + k^ω), and the paper obtains the corresponding O(d^2 + k^ω) target for positive definite systems.Source: §1 · p. 2, §1.1 · p. 4

1 Introduction

• The approach combines recursive preconditioning with matrix sketching, oblivious subspace embeddings, Woodbury-based reductions, and structure-specific frameworks for regression and positive definite systems.The paper develops a warm-up framework followed by more specialized recursive schemes.Source: §1 · p. 3, §1.2 · p. 6

1.1 Main Results

• The framework yields a first nearly linear-time multiplicative nuclear norm approximation for dense matrices and nearly linear-time approximations for Schatten p-norms when p ∈ (1/2, 2).The nuclear norm algorithm runs in O((nnz(A) + d^2)poly(1/ϵ)) time.Source: §1 · p. 3, §1.1 · p. 5
• The generalized averaged condition number uses a generalized mean over non-top-k singular-value ratios, making lower p values correspond to broader matrix classes.A matrix is (k,p)-well-conditioned when this quantity is O(1), and the measure is monotone in p.Source: §1.1 · pp. 3–4
• Regression can be solved whp. in O((nnz(A) + d^2) log(1/ϵ)) + O(k^ω) time when A is (k,p)-well-conditioned for p > 1/2.The result applies to A ∈ R^{n×d} and returns an ϵ-approximate least-squares solution.Source: §1.1 · p. 4
• Positive definite systems can be solved whp. in O(d^2 log(1/ϵ)) + O(k^ω) time when M is (k,p)-well-conditioned for p > 1/4.This relaxes the regression threshold and exploits positive definiteness to match the conditional lower bound.Source: §1.1 · p. 4
• The algorithms replace prior running-time trade-offs of O(d^2 + dk^{ω−1}) and O(d^{2.065} + k^ω), closing the remaining gap for k between d^0.73 and d^0.87.The new bounds combine the favorable dependence on d and k from the two prior approaches.Source: §1 · p. 2, §1.1 · p. 5

1.2 Related Work

• Prior randomized methods use fast matrix multiplication, block-coordinate techniques, or sketching-based preconditioners, with bottlenecks including d^ω and weaker preconditioners.The paper addresses the latter limitation by chaining many weak preconditioners.Source: §1.2 · p. 6

2.1 Warm-up: Recursive Regression Solver

• Regularized preconditioning chains recursively replace a regression system with progressively smaller sketches, making top-level work dominate at approximately O~(nnz(A) + d^2) time.The recursion stops near dimension O~(k), where Woodbury-based dual preconditioning and low-rank structure reduce construction costs to O~(T·nnz(A) + k^ω).Source: §2.1 · pp. 7–8
• For any η > 0, the solver has almost-linear running time ˜O(nnz(A) + d^2κ̄_k,1+η(A) log(d)O(1/η)) after ˜O(nnz(A)+k^ω) preprocessing, scaling with averaged condition number κ̄_k,1+η(A).Source: §2.1 · p. 9

2.2 Alternating Primal-Dual Regression Solver

• Alternating primal and dual preconditioning reduces both dimensions of the regression matrix, yielding O~(nnz(A) + d^2κ̄_k,1/2+η(A) log(d)O(1/η)) time after O~(nnz(A)+k^ω) preprocessing.The method sketches A on both sides and estimates unknown regularization parameters inductively by verifying spectral approximation conditions with power-method norm estimates.Source: §2.2 · pp. 9–10

2.3 Implicit Dual Solver for PD Systems

• For positive definite systems, an implicit dual solver adapts Nyström approximations and regularized inner systems into a recursive reduction, improving conditioning dependence beyond regression.Because only M is accessible, sketching occurs externally through C = MS^⊤ and W = SMS^⊤; regularizing W enables reduction to a smaller regularized positive definite system.Source: §2.3 · pp. 10–11
• Implicit dual preconditioning reduces positive-definite systems recursively through constant-factor approximations, ultimately using the next-level regularized system as a preconditioner.The reduction uses the Woodbury identity and recursively tunes decreasing sketch sizes and increasing regularizations.Source: §2.3 · p. 11
• The implicit dual solver improves conditioning dependence because spectral bounds use singular values of A, the square roots of M = AA^T's eigenvalues.It recovers Theorem 4 after approximately nnz(A) + k^ω preprocessing, with runtime depending on the averaged conditioning measure and η > 0.Source: §2.3 · p. 12

2.4 Applications: Spectrum Approximation

• The spectrum-approximation framework uses regularized linear solvers, rational polynomials, and trace estimation to approximate singular-value histograms and norms.The framework applies to Schatten, Ky Fan, and Orlicz norms, and its systems naturally align with the paper's well-conditioning model.Source: §2.4 · p. 12
• The paper identifies (0, p)-well-conditioning as exactly matching the systems needed for Schatten p-norm approximation, reducing approximation to solving such systems.Using the primal-dual regression solver with p = 1 recovers the nuclear norm guarantee in Theorem 5; nearly linear guarantees extend to p > 1/2, or p > 1/4 for positive-definite A, while optimized trade-offs give state-of-the-art complexity for fixed p ∈ (0, 1/2).Source: §2.4 · p. 12

• The paper defines eigenvalues for symmetric matrices, singular values for rectangular matrices, condition number κ(A), Loewner order, spectral and Frobenius norms, and normalized tail quantities.Source: §3 · p. 13
• The notation ˜O(T) hides polylogarithmic factors, while whp. denotes success probability 1 − 1/(n+d)^c for adjustable c.The runtime convention also adds n+d to nnz(A) expressions.Source: §3 · p. 13
• Preconditioned AGD converts a solver for N into an ε-solver for M when M ⪯ N ⪯ κM, using O(√κ log(1/ε)) applications.The cited procedure requires a 1/(10κ)-solver for N and adds O(n√κ log(1/ε)) time.Source: §3 · p. 13
• An (ε,ν)-embedding regularizes a matrix sketch, and OSE moments imply such embeddings through Markov’s inequality.These definitions support the randomized sketching guarantees used by the recursive algorithms.Source: §3 · pp. 13–14
• Sparse embedding matrices use independent columns with randomly placed ±1/b entries, with stated sketch-size and sparsity bounds guaranteeing OSE moments.The construction has s = O((d+log(1/(δε)))/ε^2) and b = O(log^2(d/(δε))/ε + log^3(d/(δε))).Source: §3 · p. 14

4 Warm-up: Recursive Regression Solver

• The warm-up develops a recursive preconditioning approach for regression and linear systems in A⊤A, introducing ideas used later for the main regression algorithm.The method does not fully recover Theorem 3 but establishes key proof techniques.Source: §4 · p. 14

4.1 Reduction Tools

• Sparse subspace embeddings sketch wide matrices and yield a preconditioner for AA⊤ + νI, while an algorithm returns an ε-solver for A⊤A + νI.The algorithm runs in ˜O(nnz(A) log^3(s/δ) + (s + log(1/δ))^ω) time with probability 1 − δ.Source: §4.1 · p. 15

4.2 Recursive Preconditioning

• A general recursive preconditioning guarantee solves the first matrix in a spectrally related preconditioning chain by recursively invoking solvers for later matrices.The framework is designed as a general-purpose method for the simple regression solver, while later sections require more elaborate recursions.Source: §4.2 · pp. 15–16

4.3 Regularized Preconditioning for Regression

• Regularized preconditioning chains combine monotone regularization with recursive preconditioning to produce regression solvers, including a ˜O(d^2) + O(k^ω)-time solver construction for A⊤A + ν0I.The chain framework applies to systems A⊤A + λI and yields Theorem 1 through a reduction from tall least-squares regression.Source: §4.3 · pp. 17–18

4.4 Improved Conditioning Dependence

• A faster-decreasing sketch-size schedule with νt chosen near Σkt(A) improves the conditioning dependence from κ̄k,2 toward κ̄k,1+η, assuming approximate singular values are available.Under the stated assumptions, the resulting solver is developed in ˜O(d^2 + k^ω) time with high probability.Source: §4.4 · p. 19
• The analysis uses generalized-mean bounds and a technical sequence argument to control conditioning terms across recursion levels, while logarithmic factors retain a simplifying dependence on d.A footnote notes that more careful termination could potentially remove the d factor inside these logarithms by switching to simpler iterative methods in the well-conditioned regime.Source: §4.4 · p. 21
• The solver’s recursion can be bounded after ˜O(d^2) + O(k^ω) preprocessing, with Lemma 23 controlling the per-round cost through the decaying sequence k_t.Lemma 23 bounds the term corresponding to the t-th recursive round, and combining it with Theorem 21 establishes the improved running-time guarantee.Source: §4.4 · pp. 20–22
• Theorem 24 gives a high-probability regression solver achieving relative residual error ϵ under approximate singular-value information and improved conditioning-dependent running time.The algorithm takes A, b, ϵ, k, and estimates ˜σ_i ≈2 σ_i(A)^2, and outputs x_out satisfying ∥Ax_out − Ax*∥ ≤ ϵ∥Ax*∥.Source: §4.4 · p. 21
• Accurate singular-value estimates are not essential: parallel executions over geometrically spaced parameter guesses recover the desired solution with an exp(O(log(d∥A∥^2/ℓ) log log(d∥A∥^2/ℓ))) execution overhead.The guessing procedure uses computable Frobenius-norm information and selects the candidate with the lowest objective value within the time budget.Source: §4.4 · p. 22

5.1 Reduction Tools

• Dual preconditioning converts approximations between A A^T + νI and B B^T + νI into solvers for the corresponding primal systems, allowing the two dimensions to differ.The reduction uses Woodbury-based solver transformations and applies the supplied solver only logarithmically many times.Source: §5.1 · pp. 22–23

5.2 Primal-Dual Recursive Preconditioning

• The primal-dual chain alternates between matrices A_t and B_t, reducing first one dimension and then the other while increasing regularization.This chain provides the recursive structure used to transfer solvers between primal and dual systems.Source: §5.2 · p. 23

5.3 Regression Algorithm

• The solver handles any (k, p)-well-conditioned regression system with p > 1/2 in nearly linear time, recovering Theorem 3.The result extends beyond strict k-well-conditioning by using averaged spectral conditions.Source: §5.3 · p. 24
• The algorithm finds regularization parameters by testing spectral approximation on candidates ν̂_t,i = ν_T / 2^i until the condition fails.A failed test implies a usable upper bound on the next spectral-sum scale, enabling the chain to be extended inductively.Source: §5.3 · pp. 24–26
• The final regression solver combines recursive solves, parameter testing, and O(log(1/ϵ)) refinement applications to achieve the claimed running time.The construction cost includes ˜O(nnz(A) + d^2) preprocessing and O(k^ω) terminal work.Source: §5.3 · pp. 24, 26

5.4 Testing Spectral Approximation

• The tester converts spectral approximation into spectral-norm estimation and uses an inexact power method with black-box approximate matrix-vector products.The power method estimates the relevant norms with high probability, and the binary output distinguishes approximation factors 4 and 2.Source: §5.4 · pp. 26–27

6 Implicit Dual Solver for Positive Definite Systems

• The implicit-dual framework is specialized to positive definite structure, enabling weaker conditioning assumptions than the corresponding regression formulation.The paper presents this as a structural advantage of positive definite inputs.Source: §6 · p. 27, §6.3 · p. 31

6.1 Reduction Tools

• The main reduction uses a low-rank approximation B^T B of A^T A to solve A A^T + νI using only products with A A^T and A B^T.This implicit dual formulation avoids direct access to A and B during recursive preconditioning.Source: §6.1 · p. 28

6.2 Implicit Dual Recursive Preconditioning

• Chained subspace embeddings preserve the OSE property, allowing recursively constructed matrices A_t to form a valid regularized preconditioning chain with high probability.The matrices are built recursively as A_t = S_t S_{t−1} ... S_1 A_0 rather than by independently sketching the original matrix.Source: §6.2 · pp. 29–30

6.3 Positive Definite Solver

• The positive definite solver provides a T-time ϵ-solver in ˜O(d^2) + O(k^ω) time with high probability.The algorithm is given estimates of κ(M), λ_d(M), and λ_2k(M), and the theorem follows after parameter selection.Source: §6.3 · pp. 31–32
• The algorithm works implicitly with M_t = A_t A_t^T and related cross-products, whose total construction cost is ˜O(d^2), while the terminal inverse costs O(k^ω).At the final level, the sketched dimension is O(k) up to polylogarithmic terms.Source: §6.3 · p. 31
• Regularization parameters are selected by testing spectral approximation between consecutive implicit matrices with an inexact power method.The tester uses only products with A A^T, B B^T, and A B^T and distinguishes approximation factors 4 and 2.Source: §6.3 · p. 32, §6.4 · pp. 32–33

• The reduction converts Schatten p-norm approximation into solving systems involving A^T A + λI, enabling the paper’s linear-system solvers to accelerate norm estimation.The framework applies for p in (0, 2) and uses a carefully chosen regularization parameter λ.Source: §7 · p. 34
• Nearly-linear-time constant-factor approximation algorithms follow for Schatten p-norms with p > 1/2 for general matrices and p > 1/4 for positive-definite matrices.Source: §7 · p. 34
• The method extends to all ε in (0, 1) and p in (0, 2) for general-matrix Schatten p-norm approximation.Source: §7 · p. 34
• The nuclear norm becomes the first Schatten p-norm with a nearly-linear-time dense approximation algorithm, while prior runtimes were Ω(d^(2+θ_p)) for p in (1/2, 2).Source: §7 · p. 34
• For p in (0, 1/2], the algorithms match the best known time complexity and improve the p = 1/4 runtime from d^2.2336 to d^2.1103 in the dense component.Source: §7 · p. 34
• A subspace embedding reduces the row dimension to approximately d/ε^2 with additional nearly O(nnz(A)/ε) preprocessing time before applying the solver-based approximation.Source: §7 · p. 34