Source-linked AI summary
Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
Xiangrui Meng, Michael W. Mahoney
TL;DR
Fast low-distortion ℓp subspace embeddings are sought for large overconstrained regression and related linear-algebra problems. The paper constructs input-sparsity-time embeddings for p ∈ [1,2), extends them to near-input-sparsity-time subspace embeddings and regression, and improves the embedding dimension to O(d^{3+p/2} log(1/ε) / ε^2) without increasing complexity.
Problem
Fast computation of (1+ε)-approximate solutions to overconstrained ℓp regression is important for large-scale data applications, motivating faster low-distortion subspace embeddings.
Method
The paper constructs low-distortion sparse ℓp subspace embeddings in input-sparsity time and couples them with fast subspace-preserving sampling for regression and near-isometric embeddings.
Results
The embeddings achieve O(poly(d)) distortion with ΠA computable in O(nnz(A)) time, while sampling yields (1±ε)-distortion embeddings and (1+ε)-approximate ℓp regression in O(nnz(A) · log n + poly(d) log(1/ε)/ε^2) time.
Takeaways & Limitations
The results extend input-sparsity-time subspace embeddings across p ∈ [1,2) and improve the embedding dimension to O(d^{3+p/2} log(1/ε) / ε^2) without increasing complexity.
Takeaways & Limitations
The ℓ1 discussion concerns data-dependent embeddings for points in a subspace, rather than oblivious embeddings for arbitrary point sets, and assumes n ≫ poly(d) ≥ d ≫ log n.
Abstract
from arXiv · showhide
Low-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for linear algebra problems. We show that, given a matrix $A \in \R^{n \times d}$ with $n \gg d$ and a $p \in [1, 2)$, with a constant probability, we can construct a low-distortion embedding matrix $Π\in \R^{O(\poly(d)) \times n}$ that embeds $\A_p$, the $\ell_p$ subspace spanned by $A$'s columns, into $(\R^{O(\poly(d))}, \| \cdot \|_p)$; the distortion of our embeddings is only $O(\poly(d))$, and we can compute $ΠA$ in $O(\nnz(A))$ time, i.e., input-sparsity time. Our result generalizes the input-sparsity time $\ell_2$ subspace embedding by Clarkson and Woodruff [STOC'13]; and for completeness, we present a simpler and improved analysis of their construction for $\ell_2$. These input-sparsity time $\ell_p$ embeddings are optimal, up to constants, in terms of their running time; and the improved running time propagates to applications such as $(1\pm ε)$-distortion $\ell_p$ subspace embedding and relative-error $\ell_p$ regression. For $\ell_2$, we show that a $(1+ε)$-approximate solution to the $\ell_2$ regression problem specified by the matrix $A$ and a vector $b \in \R^n$ can be computed in $O(\nnz(A) + d^3 \log(d/ε) /ε^2)$ time; and for $\ell_p$, via a subspace-preserving sampling procedure, we show that a $(1\pm ε)$-distortion embedding of $\A_p$ into $\R^{O(\poly(d))}$ can be computed in $O(\nnz(A) \cdot \log n)$ time, and we also show that a $(1+ε)$-approximate solution to the $\ell_p$ regression problem $\min_{x \in \R^d} \|A x - b\|_p$ can be computed in $O(\nnz(A) \cdot \log n + \poly(d) \log(1/ε)/ε^2)$ time. Moreover, we can improve the embedding dimension or equivalently the sample size to $O(d^{3+p/2} \log(1/ε) / ε^2)$ without increasing the complexity.
1 Introduction
The paper targets faster randomized algorithms for overconstrained ℓp regression and subspace embeddings, especially when sparse inputs make conventional Ω(nd log d) methods costly. It develops input-sparsity-time low-distortion embeddings for p ∈ [1,2] and extends them to accurate embeddings and regression algorithms.
- Motivation: Overconstrained ℓp regression seeks a (1 + ϵ)-approximate solution for A ∈ R^n×d with n > d, including robust ℓ1 regression.ℓ1 regression is less sensitive to outliers than least squares.
- Motivation: Ω(nd log d) time is required by many existing randomized algorithms, motivating methods that exploit sparse inputs.The paper identifies input-sparsity time as a remedy for large costs when A is very sparse.
- Main contributions: Input-sparsity-time low-distortion ℓp subspace embeddings are provided for every p ∈ [1,2], with applications to nearly input-sparsity-time ℓp regression.The approach couples the embeddings with fast subspace-preserving sampling.
- Main contributions: For ℓ2, the paper simplifies and improves the analysis of an existing (1 ± ϵ)-distortion embedding and propagates the improvement to regression, low-rank approximation, and leverage-score estimation.The analysis avoids splitting the subspace into heavy hitters and their complement.
- Main contributions: For ℓ1 and p ∈ (1,2), sparse Π matrices have ΠA computable in O(nnz(A)) time, while sampling yields (1 ± ϵ) embeddings and (1 + ϵ)-approximate regression.The p ∈ (1,2) analysis uses tail bounds for p-stable distributions.
- Main contributions: The embedding dimension s = O(poly(d) log(1/ϵ)/ϵ^2) can be improved by decoupling the polynomial-d and accuracy factors without increasing overall complexity.A further round of sampling and conditioning yields a small poly(d) factor times log(1/ϵ)/ϵ^2.
2 Background
The background develops conditioning and sampling as the bridge between low-distortion subspace embeddings and regression. It also introduces p-stable distributions and their tail bounds as the probabilistic tools behind the input-sparsity constructions.
- Notation and scope: The paper studies embedding the ℓp subspace A_p into R^poly(d) with poly(d) or (1 ± ϵ) distortion, assuming n ≫ poly(d) ≥ d ≫ log n.It also assumes small regression instances independent of n can be solved separately.
- Conditioning: The paper distinguishes ℓp-norm conditioning from (α, β, p)-conditioning and uses their equivalence to define well-conditioning independent of n.Well-conditioning means κp(A) or κ̄p(A) = O(poly(d)).
- Conditioning: A low-distortion embedding produces a well-conditioned basis AR^-1, linking embedding quality to subsequent regression algorithms.The QR factor R of ΠA is used to form AR^-1, whose ℓp conditioning is bounded by a polynomial in d.
- Conditioning: Conditioning can be obtained through embeddings or ellipsoidal rounding, with fast O(d)-conditioning available in O(nd^3 log n) time.The stated conditioning guarantee is κp(AR^-1) ≤ 2d.
- Sampling and regression: Fast subspace-preserving sampling takes O(nnz(A) · log n) time once AR^-1 is well-conditioned and constructs a (1 ± ϵ)-distortion embedding.The sampling matrix has one nonzero element per row.
- Sampling and regression: Sampling the subspace spanned by A and b and solving the subsampled problem yields a (1 + ϵ)-approximate ℓp regression solution.The subsampled optimizer is evaluated through the sampling-based regression lemma.
3 Main Results for ℓ2 Embedding
The paper gives a simpler analysis of Clarkson and Woodruff’s ℓ2 embedding, improving its dimension bound while retaining input-sparsity computation and enabling faster regression.
- Theorem 1: s = (d^2 + d)/(ϵ^2δ) suffices for (1 ± ϵ)-distortion ℓ2 embedding with probability at least 1 − δ.The embedding uses Π = SD with independently hashed standard-basis columns and independent random signs.
- Running time: O(nnz(A)) time computes ΠA, which is optimal up to constant factors for general inputs.The paper argues that important rows may need to be observed, requiring a scan of a constant portion of the input.
- Applications: Theorem 1 propagates to related applications, including ℓ2 regression, low-rank approximation, and approximate leverage-score computation.The paper states the regression improvement explicitly while noting the same propagation to the other applications.
- Applications: With constant probability, a (1 + ϵ)-approximate ℓ2 regression solution can be computed in O(nnz(A) + T^2(ϵ; d^2/ϵ^2, d)) time.This corollary combines the improved embedding with a prior regression theorem.
4 Main Results for ℓ1 Embedding
The paper constructs input-sparsity-time ℓ1 embeddings with polynomial distortion and combines them with sampling to obtain nearly input-sparsity-time regression and near-isometric embeddings.
- Low-distortion embedding: s = ωd^5 log^5 d yields a constant-probability ℓ1 embedding with distortion between 1/O(d^2 log^2 d) and O(d log d).The construction hashes columns and applies independent standard Cauchy variables diagonally.
- Running time: O(nnz(A)) time computes ΠA for the low-distortion ℓ1 embedding.The construction differs from the ℓ2 counterpart by using Cauchy variables instead of random signs.
- Analysis quality: The distortion analysis may overstate the construction by an O(d log^3 d) factor, while a perfectly hashed top-d-row case has distortion approximately O(d^2).The paper attributes this gap to artifacts in the analysis rather than to the hashing construction in that case.
- Near-isometric embedding: O(nnz(A)·log n) time computes an ℓ1 sampling embedding with s = O(poly(d) log(1/ϵ)/ϵ^2) and distortion 1 ± ϵ.This combines the low-distortion embedding with subspace-preserving sampling.
- Regression application: With constant probability, ℓ1 regression is approximated within 1 + ϵ in O(nnz(A)·log n + T^1(ϵ; poly(d) log(1/ϵ)/ϵ^2, d)) time.The result is obtained through Algorithm 1 and the associated embedding and sampling steps.
- Scope: The ℓ1 dimension-reduction result applies to subspaces using data-dependent sampling, not arbitrary point sets with oblivious embeddings.This distinguishes the setting from impossibility results for general ℓ1 dimension reduction.
5 Main Results for ℓp Embedding
The paper extends input-sparsity-time low-distortion subspace embeddings from ℓ1 to ℓp for p ∈ (1,2), using p-stable distributions and tail inequalities. These embeddings yield nearly input-sparsity-time (1 ± ϵ)-distortion embeddings and ℓp regression algorithms.
- Technical approach: p-stable distributions are analyzed by ordering Cauchy, p-stable, and Gaussian variables, enabling upper and lower tail inequalities for general p.The resulting inequalities replace the Cauchy bounds used for ℓ1 embeddings.
- Low-distortion embedding: s = ωd^5 log^5 d gives a constant-probability low-distortion ℓp embedding with ΠA computable in O(nnz(A)) time.The construction uses a uniformly sampled-and-scaled sparse matrix Π = SD.
- Applications: O(nnz(A) · log n) time suffices for a (1 ± ϵ)-distortion ℓp embedding with s = O(poly(d) log(1/ϵ)/ϵ^2).This combines the input-sparsity embedding with fast subspace-preserving sampling.
- Applications: The resulting embeddings improve on the O(nd log n)-time construction of Clarkson et al. for the stated ℓp setting.The construction requires only O(poly(d)) storage rather than solving an intermediate rounding problem of size O(n/poly(d)) × d.
- Applications: The improved embeddings propagate to a nearly input-sparsity-time algorithm for approximate ℓp regression.The paper states a constant-probability (1 + ϵ)-approximate regression result, with further runtime details in Corollary 3.
- Dense alternative: Dense p-stable embeddings use s = ωd log d rows and have better embedding dimension and condition-number quality, but require O(nnz(A) · d log d) application time.The paper contrasts this with the sparse construction’s faster runtime.
6 Improving the Embedding Dimension
The paper addresses the large polynomial dependence on d in the standard embedding dimension by decoupling it from the log(1/ϵ)/ϵ^2 factor. A second sampling-and-conditioning round preserves the overall O(nnz(A) · log n) complexity while reducing the dimension.
- Motivation: The standard dimension O(poly(d) log(1/ϵ)/ϵ^2) directly multiplies a somewhat large polynomial in d by the accuracy factor.The paper identifies this dependence as undesirable for subspace embeddings and regression.
- Method: Another round of sampling and conditioning decouples the large polynomial in d from log(1/ϵ)/ϵ^2 without increasing complexity.Algorithm 2 first computes a low-distortion embedding, conditions the basis, and then applies subspace-preserving sampling.
- Result: O(d^(3+p/2) log(1/ϵ)/ϵ^2) rows suffice for a (1 ± ϵ)-distortion embedding in O(nnz(A) · log n) time.This is the guarantee of Theorem 7 for p ∈ [1,2).
- Regression consequence: The improved dimension reduces the size of the subsampled regression problem and therefore the overall regression runtime.The corresponding subsampled problem has size O(d^(3+p/2) log(1/ϵ)/ϵ^2) × d.
A.1 Proof of Theorem 1 ((1 ± ϵ)-distortion Embedding for ℓ2)
The ℓ2 proof directly bounds how the embedding perturbs U^T U for an orthonormal basis U, rather than separately controlling every vector in the subspace. A Frobenius-norm bound then yields the desired spectral guarantee.
- Proof strategy: The proof starts with an orthonormal basis U for range(A) and controls perturbation of U^T U.This avoids proving the embedding inequality separately for every z ∈ R^d.
- Moment bound: The analysis expands the embedding perturbation using the entries of S, D, and U and evaluates the needed expectations.The proof uses the stated element definitions and moment identities.
- Conclusion: s = (d^2 + d)/(ϵ^2δ) leads, via Markov’s inequality, to ∥X − I∥_2 ≤ ϵ with probability at least 1 − δ.The argument first bounds the Frobenius norm and then uses spectral-norm domination.
A.2 Proof of Theorem 2 (Low-distortion Embedding for ℓ1)
The ℓ1 proof uses an Auerbach-conditioned basis and divides coordinates by ℓ1 leverage into high- and low-leverage sets. Hashing and Cauchy scaling then establish upper and lower bounds over both parts with constant probability.
- Basis and leverage partition: An Auerbach basis provides unit ℓ1-norm columns and ∥x∥∞ ≤ ∥Ux∥1 for every coefficient vector x.The basis is used to condition the column space before analyzing the embedding.
- Basis and leverage partition: The proof partitions rows into H = {j | v_j ≥ τ} and L = {j | v_j < τ}, with at most d high-leverage rows.It further splits L according to whether hashed buckets overlap the high-leverage image.
- Probability analysis: The combined event gives Π = SC the desired low-distortion property with probability at least 0.5.This completes the proof of Theorem 2.
- Low-leverage analysis: The low-leverage analysis uses an ϵ-net and union bounds to extend fixed-vector lower bounds to all vectors in Y^L.The net has at most (3d/ϵ)^d elements.
- Probability analysis: The events governing upper bounds, low-leverage behavior, hashing, and Cauchy tails each hold with probability at least 0.92 under the chosen parameters.The parameter choices include ω1, ω2, ω3, and ω4 as specified by the lemmas.
A.3 Proof of Corollary 2 (Fast ℓ1 Regression)
Conditioned on successful embedding and sampling steps, Algorithm 1 yields a relative-error ℓ1 regression guarantee and the stated running time.
- Constant-probability success of Steps 2 and 4 enables the subsequent regression guarantee.
- ∥Aˆx−b∥1 is bounded by ((1 + ϵ/4)/(1 − ϵ/4)) times the sketched optimum, which is at most (1 + ϵ/4)^2 times the optimum.The final inequality uses ϵ < 1/2.
- O(nnz(A) · log n) plus T1(ϵ/4; O(poly(d) log(1/ϵ)/ϵ^2), d) time is obtained for Algorithm 1.Step 2 takes O(nnz(A)), Step 3 takes O(poly(d)), and Step 4 takes O(nnz(A) · log n).
A.4 Proof of Lemma 8
Lemma 8 analyzes tail behavior for p-stable distributions, including the Cauchy and Gaussian cases, to support later embedding arguments.
- Lemma 23 records an asymptotic result for X sampled from a p-stable distribution Dp with p ∈ [1, 2).
- The Cauchy distribution is treated separately in the tail analysis.
- All p-stable distributions with p ∈ [1, 2] have finite, positive density at x = 0, supporting the existence of α′′.
- The Gaussian tail converges to zero much faster than t−1, allowing analogous arguments to obtain βp.
A.5 Proof of Lemma 9 (Upper Tail Inequality for p-stable Distributions)
The upper-tail proof compares p-stable variables with transformed Cauchy or Gaussian variables, then extends fixed-vector bounds to the full subspace using a net argument.
- Cauchy-transformed variables satisfy αp|Ci| ≥ |Xi|p, enabling an upper-tail comparison for p-stable samples.Ci is constructed from the CDF transform of Xi and follows the standard Cauchy distribution.
- The resulting bound is combined with Lemma 5, while the Gaussian case uses independent standard Gaussian variables and Lemma 8.
- The lower-tail inequality from Lemma 7 completes the proof.
- For a conditioned basis matrix U, the proof defines Y from vectors Ux with ∥x∥q = 1 and establishes a constant-probability bound over Y.
- Choosing s = ωd log d sufficiently large and applying an ϵ-net argument yields a simultaneous lower bound over Y with constant probability.
- Algorithm 2's steps succeed with constant probability, and the conditioning parameter satisfies κp(AR−1) = 6d while ¯κp(AR−1) ≤ 6d^(1/p+1).These bounds determine the embedding dimension through Lemma 3.