Source-linked AI summary
Faster Least Squares Approximation
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, Tamas Sarlos
TL;DR
Overconstrained least-squares systems generally lack exact solutions, and existing exact methods require O(nd^2) time. The paper proposes two randomized reductions using a Randomized Hadamard Transform, followed by sampling or sparse projection, and obtains accurate relative-error approximations with O(nd log d) computation under stated conditions.
Problem
Overconstrained least-squares systems often have no exact solution, while existing exact methods require O(nd^2) time.
Method
The paper applies a Randomized Hadamard Transform, then either uniformly samples constraints or uses a sparse random projection before solving the reduced least-squares problem.
Results
The randomized algorithms provide accurate relative-error approximations to the optimal value and solution vector, computable in O(nd log d) time when n is sufficiently larger than d.
Takeaways & Limitations
Reduced least-squares problems can provide the paper's relative-error guarantees while offering faster computation than existing exact algorithms under the stated conditions.
Takeaways & Limitations
The paper identifies relaxing the constraints on n for either algorithm as an open problem.
Abstract
from arXiv · showhide
Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets $n$ be the number of constraints and $d$ be the number of variables, with $n \gg d$. Then, existing exact methods find a solution vector in $O(nd^2)$ time. We present two randomized algorithms that provide very accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard Transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if $n$ is sufficiently larger than $d$, the approximate solution can be computed in $O(nd \log d)$ time.
1 Introduction
The paper develops randomized least-squares algorithms that approximate the optimal solution more quickly than exact methods for overconstrained systems. Both use a Randomized Hadamard Transform before reducing the problem through sampling or sparse projection, achieving O(nd log d) computation under stated conditions.
- Motivation: Least squares finds an approximate solution by minimizing the squared residual when Ax = b has no exact solution.The setting uses A ∈ R^n×d and b ∈ R^n, typically with n ≫ d.
- Existing methods: Direct methods such as QR solve overconstrained least squares in O(nd^2) time, while normal equations can square the input matrix's condition number.The SVD also gives an expression for the optimal solution vector.
- Our results: The paper introduces two randomized algorithms that provide accurate relative-error approximations to the minimal ℓ2-norm solution vector faster than existing exact algorithms.The algorithms target a large class of overconstrained least-squares problems.
- Guarantees: With probability at least .8, the randomized output satisfies the theorem's stated approximation guarantees for the solution and objective under its assumptions.The success probability can be amplified by repeating the algorithm.
- Runtime and scope: O(nd ln d) computation is possible when n is sufficiently larger than d, with the two algorithms having different stated n–d conditions.The first algorithm is simpler, while the second has a marginally less restrictive connection between n and d.
- Our results: Both algorithms first apply the Randomized Hadamard Transform, then solve a reduced least-squares problem formed by sampled constraints or projected coordinates.The first samples r constraints uniformly; the second applies a k×n sparse projection with k = O(d/ε).
- Limitations: An open problem is relaxing the constraints on n for either proposed algorithm.The second algorithm's assumption is described as marginally less restrictive.
- Empirical context: The paper reports that related numerical implementations performed well for certain matrices as small as thousands of rows by hundreds of columns, although it provides no empirical evaluation itself.These demonstrations followed the earlier technical report.
2 Preliminaries
The preliminaries establish notation for vectors, matrices, norms, singular-value decompositions, and orthogonal complements. They also introduce the Randomized Hadamard Transform, which spreads vector energy and can be computed efficiently.
- Notation: The notation defines [n] as {1, 2, ..., n}, matrix rows and columns, expectations, and variances.
- Linear algebra background: The SVD represents A using left singular vectors, non-zero singular values, and right singular vectors.The pseudoinverse and condition number are expressed through these singular values.
- Linear algebra background: The condition number is κ(A) = σmax(A)/σmin(A), comparing the largest and smallest non-zero singular values.
- Linear algebra background: The optimal least-squares residual is characterized using an orthogonal complement to the column space of A.
- Probability tools: The preliminaries introduce Markov’s inequality and the union bound as probability tools used later in the analysis.
- Randomized Hadamard Transform: The Randomized Hadamard Transform is HD, where H is normalized and D has independent random ±1 diagonal entries.Applied to a vector, HD spreads out its energy by controlling the infinity norm.
3 Our algorithms as preconditioners
The algorithms precondition least-squares inputs with a random matrix, reduce the problem through sampling or projection, and solve the smaller regression. A deterministic lemma links suitable embedding conditions to relative-error guarantees, with an additional assumption needed for a stronger solution-vector bound.
- Preconditioning: Both algorithms replace the original regression with a preconditioned problem using X = ST HD for sampling or X = THD for projection.The transform first mixes the rows, after which constraints are sampled or projected.
- Solving the reduced problem: The reduced least-squares problem can be solved deterministically, while CGNR offers an iterative alternative whose time depends on κ(XA), r, d, and ln(1/ε).
- Structural conditions: Condition (8) makes XU_A an approximate isometry by keeping its singular values near one.
- Structural conditions: Condition (9) requires the transformed residual component Xb⊥ to remain approximately orthogonal to XU_A.
- Structural guarantee: Lemma 1 states that conditions (8) and (9) on X yield relative-error bounds for the reduced problem’s solution vector.The lemma is deterministic; randomized failure probabilities enter only when the algorithms are shown to satisfy those conditions.
- Assumption and strengthened bound: Without assumptions on b, the solution-vector bound may be weak; assuming a constant fraction of b lies in A’s column space strengthens it.
4 A sampling-based randomized algorithm
The sampling-based algorithm preprocesses the least-squares instance with a Randomized Hadamard Transform, uniformly samples and rescales constraints, and solves the resulting smaller problem. Its guarantees follow from concentration properties of the transformed matrix and sampled products, with running-time improvements under stated assumptions.
- Algorithm and construction: Algorithm 1 applies the Randomized Hadamard Transform, uniformly samples r constraints, rescales them, and solves the induced smaller least-squares problem.Only the sampled rows and corresponding entries are accessed after preprocessing.
- Accuracy guarantee: With probability at least .8, Theorem 2 establishes the stated approximation guarantees for the returned vector ˜xopt.The theorem combines the sampling lemmas with structural properties of the transformed least-squares instance.
- Geometric interpretation: The approximation error for ˜xopt grows with the tangent of the angle between b and the column space of A under the theorem's geometric assumption.The paper notes that weaker assumptions could also yield improvements over O(nd^2), but focuses on the stated setting for clarity.
5 A projection-based randomized algorithm
Algorithm 2 preprocesses the least-squares instance with a Randomized Hadamard Transform, applies a sparse random projection, and solves the resulting smaller problem. Theorem 3 provides constant-probability approximation guarantees under stated parameter choices.
- Algorithm 2: Algorithm 2 applies the Randomized Hadamard Transform before constructing a smaller problem through sparse projection.The projection uses a k×n sparse matrix T on the preprocessed matrix and right-hand side.
- Algorithm 2: The projected least-squares problem uses THDA ∈ Rk×d and THDb ∈ Rk, returning the minimum ℓ2-norm solution.The returned vector is computed as (THDA)†THDb.
- Guarantees: Theorem 3 states that, with constant probability, the returned vector satisfies the theorem’s approximation claims when q and k use the specified parameter values.The proof establishes the required conditions for THD and combines them with an earlier quality lemma.
- Projection analysis: The sparse projection is designed for well-spread vectors, a condition ensured by Randomized Hadamard preprocessing.Sparse projection preserves the needed behavior when the vector’s infinity-to-2-norm ratio is sufficiently small.
- Guarantees: The analysis shows that all singular values of THDUA are close to one with probability at least .95 under the lemma’s conditions.This establishes one of the conditions used for Algorithm 2’s accuracy guarantee.
6 Appendix
The appendix develops concentration and sampling arguments used to analyze randomized matrix constructions. It includes an exactly sampled-column algorithm and moment calculations for sparse projection inner products.
- Column sampling: The Exactly(c) algorithm constructs C from c rescaled columns of A using sampling probabilities satisfying the theorem’s conditions.Theorem 4 assumes ∥A∥2 ≤ 1 and imposes an accuracy-dependent condition on c.
- Column sampling: Theorem 4 analyzes the approximation error of the sampled-column construction under bounded spectral norm and specified sampling assumptions.The proof views CCT as an empirical mean corresponding to the true mean AAT.
- Sparse projection moments: For sparse projection, the appendix defines ∆ as the difference between the projected and original inner products and analyzes its expectation and variance.The analysis uses independent rows and examines the index patterns that yield nonzero fourth moments.
- Sparse projection moments: The fourth-moment calculation separates four nonzero index configurations: three pairings and the case where all four indices are equal.The configurations are enumerated as cases (A)–(D).
- Sparse projection moments: The proof bounds the sparse-projection error using the assumption ∥x∥∞ ≤ α.Under this assumption, the relevant variance term is bounded using α².