The regression problem

  • A hidden parameter vector x ∈ ℝᵈ; observed variables a₁, …, a_d and a response b = Σᵢ aᵢxᵢ 49:59.
  • We run experiments: the aᵢ and b are observable, the xᵢ are what we want to solve for 50:48.
  • Stack the experiments into a tall, skinny n × d matrix A and solve Ax = b with b ∈ ℝⁿ 51:09.
  • Reality adds noise: b = Σᵢ aᵢxᵢ + noise, so we only want Ax ≈ b 52:17.
  • Least squares: x* = argmin_x ‖Ax − b‖₂ 53:06.

The closed form and its bottleneck

  • x* = (AᵀA)⁺ Aᵀ b, where ⁺ is the pseudoinverse — a generalization of the inverse that also handles A without full column rank 53:06, 53:36.
  • Cost of AᵀA: it is a d × n times n × d product; each of the d² output entries is a length-n dot product ⇒ O(nd²) 53:56, 54:42, 55:04.
  • The pseudoinverse costs only poly(d) (roughly d³), so AᵀA is the bottleneck 55:04.
  • Alternative from the problem set: solve iteratively by gradient descent 55:04, 55:52.

Subspace embeddings (Sarlós)

Definition. Π is an ε-subspace embedding for a linear subspace V if for all v ∈ V, ‖Πv‖₂² = (1 ± ε)‖v‖₂².

  • The same norm-preservation as before, but now demanded for infinitely many vectors at once 56:14.

The claim

  • If Π is an ε-subspace embedding for span(b ∪ columns of A), and x̃* = argmin_x ‖ΠAx − Πb‖, then ‖Ax̃* − b‖ ≤ ((1+ε)/(1−ε))·‖Ax* − b‖ 57:45.
  • I.e. solving the tiny sketched regression is almost as good as solving the true one 58:54.

The proof (three lines)

  1. x̃* is optimal for the sketched problem, so ‖ΠAx̃* − Πb‖ ≤ ‖ΠAx* − Πb‖ 1:00:33.
  2. Both sides are Π applied to a vector of the form Ax − b, which lives in the embedded subspace, so both are preserved to within 1 ± ε 1:00:57.
  3. Rearrange. Done 1:01:24.

The payoff

  • With Π an m × n matrix and m ≪ n, the bottleneck becomes (ΠA)ᵀ(ΠA), costing O(md²) instead of O(nd²) — an n → m swap. Space drops too 59:19, 59:54.
  • Crucially, m can be made to depend only on d, not on n at all 1:00:07.
  • The catch an audience member raises: you still have to compute ΠA. The answer is to use the Thorup–Zhang sketch, which is so sparse that ΠA is very cheap 1:01:24, 1:01:56.
flowchart LR
    A["A: n × d<br/>b: n × 1"] -->|"apply Π (m × n)"| PA["ΠA: m × d<br/>Πb: m × 1"]
    A -->|"exact: AᵀA"| T1["O(nd²)"]
    PA -->|"sketched: (ΠA)ᵀ(ΠA)"| T2["O(md²), m = O(d²/ε²)"]
    T2 --> R["x̃*: within (1+ε)/(1−ε)<br/>of optimal residual"]