Source-linked AI summary
Simple and Deterministic Matrix Sketching
Edo Liberty
TL;DR
Large-matrix sketching supports many approximate linear-algebra tasks, but existing approaches use sparsification, random row combinations, or row and column selection. The paper proposes Frequent-Directions, an extension of Frequent-Items, and reports a deterministic sketch with stated approximation guarantees, improved amortized updates, and experimentally competitive accuracy and runtime.
Problem
Compact matrix sketches are needed for approximate SVDs and low-rank approximations used in large-scale data-mining and linear-algebra tasks.
Method
Frequent-Directions extends the item-frequency streaming approach to matrices by processing rows and maintaining a compact sketch B.
Results
The sketch satisfies the stated approximation guarantee, while a modification reduces amortized update time to O(m/ε) per row.
Takeaways & Limitations
The approach offers a deterministic, simple-to-implement matrix sketching technique that can combine sketches and remains computationally competitive.
Takeaways & Limitations
The fast-multiplication SVD implementation is numerically unstable and generally recommended against, despite potentially benefiting this algorithm.
Abstract
from arXiv · showhide
We adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives the rows of a large matrix $A \in \R^{n \times m}$ one after the other in a streaming fashion. It maintains a sketch matrix $B \in \R^ {1/\eps \times m}$ such that for any unit vector $x$ [\|Ax\|^2 \ge \|Bx\|^2 \ge \|Ax\|^2 - \eps \|A\|_{f}^2 \.] Sketch updates per row in $A$ require $O(m/\eps^2)$ operations in the worst case. A slight modification of the algorithm allows for an amortized update time of $O(m/\eps)$ operations per row. The presented algorithm stands out in that it is: deterministic, simple to implement, and elementary to prove. It also experimentally produces more accurate sketches than widely used approaches while still being computationally competitive.
1 Introduction
Matrix sketching compresses large matrices for downstream numerical and data-mining tasks, especially when data arrive in distributed or streaming form. The paper extends Frequent-Items to matrices through Frequent-Directions, using compact sketches whose guarantees follow from periodically trimming directions.
- Matrix sketches support approximate SVDs and low-rank approximations used in data mining, LSI, clustering, PCA, regression, linear systems, and preconditioning.
- Large matrices are often distributed across machines, motivating pass-efficient methods that read the data only a constant number of times or in one streaming pass.
- Existing approaches sparsify matrices, randomly combine rows, or select representative rows or columns, but their objectives and pass requirements differ.
- Frequent-Directions is presented as a fourth approach based on the similarity between matrix sketching and item-frequency estimation.
- Frequent-Items stores a trimmed stream in O(1/ε) space while guaranteeing |f_j − g_j| ≤ εn for every item.
- For indicator-row matrices, item frequencies become column-direction norms, allowing Frequent-Items to produce a sketch B ∈ R^(1/ε)×m.
- Frequent-Directions periodically removes orthogonal vectors, reducing the sketch’s Frobenius norm faster than any single-direction projection and limiting directional loss.
2 The algorithm
Frequent-Directions maintains a compact sketch by repeatedly shrinking the singular values of an expanded sketch, yielding a spectral approximation with controlled Frobenius-norm error. The sketch supports amortized faster updates, combination of distributed sketches, and low-rank approximation guarantees.
- Frequent-Directions: Frequent-Directions applies an SVD-based shrinkage step to maintain the returned sketch B from an expanded matrix containing the current sketch and incoming row.The algorithm computes B's SVD, subtracts a threshold from squared singular values, zeroes the smallest resulting value, and reconstructs B.
- Approximation guarantee: The proof bounds the error for every test vector by summing per-iteration shrinkage errors, then relates their total to the Frobenius norms of A and B.The argument uses the identity connecting the expanded matrix C_i to the incoming row and previous sketch, together with the spectral norm of each shrinkage matrix.
- Running time: O(TSVD(ℓ, m)) operations are required per incoming vector in the worst case, equivalent to O(m/ε^2) for the sketch size ℓ = 1/ε.The main loop is dominated by computing the sketch SVD.
- Running time: O(m/ε) amortized operations per row are achieved by computing the SVD only after enough new rows fill the zeroed sketch rows.The modified algorithm weakens the matrix approximation bound to ∥A^T A − B^T B∥ ≤ tr(A^T A)/(cℓ).
- Parallelization and sketch combination: Sketches of separate matrix blocks can be combined by sketching the matrix formed from their rows while retaining the same type of approximation bound.This property is useful when the data matrix is distributed across many machines.
- Connection to matrix low-rank approximation: Projecting onto the leading left singular vectors of B yields a 1 + ε approximation to the optimal rank-k solution under the stated sketch-size condition.The bound includes the (k + 1)th singular value of A and the sketch covariance error; the space requirement can be asymptotically inferior in some regimes.
3 Experiments
The experiments compare Frequent-Directions with brute-force, naïve, sampling, hashing, and random-projection baselines on accuracy and running time across synthetic matrix settings. Frequent-Directions uses a modified implementation and is evaluated under varying sketch sizes and signal-to-noise ratios.
- Experimental setup: The evaluation compares Frequent-Directions with brute-force, naïve, sampling, hashing, and random projection using sketch accuracy and computational efficiency.All methods are restricted to an ℓ×m sketch except brute force, with auxiliary storage limited to o(ℓm).
- Frequent-Directions implementation: Frequent-Directions is implemented with c = 1/3, potentially returning rank ℓ/3 and guaranteeing ∥A^T A − B^T B∥ ≤ 3 · tr(A^T A)/ℓ.The modified implementation trades rank and guarantee constants for the tested update behavior.
- Synthetic data: The generated matrices contain a d-dimensional signal plus m-dimensional Gaussian noise, with signal-to-noise ratio controlled by ζ.The signal component has rank d, while additive noise is scaled by 1/ζ.
- Synthetic data: When ζ is close to or below 1, noise dominates the signal; when ζ grows, the signal becomes recoverable in spectral norm.The Frobenius norm remains noise-dominated for ζ ∈ o(m/d).
- Experimental setup: n = 10,000, m = 1000, ℓ = [10, 20, . . . , 300], d = [5, 10, 20, 50, 100], and ζ = [1, 2, . . . , 15] define the tested parameter grid.Each parameter combination is repeated 7 times, and accuracy is measured by ∥A^T A − B^T B∥.
- Accuracy results: At d = 50 and ζ = 10, Frequent-Directions performs significantly better than the three random techniques, while random methods can underperform naïve at small sketch sizes.The three random techniques perform similarly on this input, and the Frequent-Directions bound remains non-tight for large sketches.
4 Discussion
The discussion relates Frequent-Directions to prior matrix-sketching strategies and examines accuracy and runtime trade-offs. It emphasizes the additional dimensional cost of adapting item-frequency methods while noting practical efficiency and noise sensitivity.
- Connections to item-frequency methods: Matrix-sketching solutions adapted from item-frequency algorithms generally incur an additional factor of m in both running time and space.The paper gives sampling as an example of this transfer cost.
- Runtime: For a dense 10,000×1,000 matrix, hashing is almost as fast as naïve and independent of ℓ, while most other methods scale linearly with ℓ.Brute force is also independent of ℓ because it computes the complete SVD.
- Runtime: Sketching is more computationally efficient than random projections even though both require O(mℓ) operations per input row.The reported implementations are not highly optimized, so runtimes may vary with implementation choices.
- Noise sensitivity: With ℓ = 100, all sketching methods improve as ζ increases because diminishing noise concentrates rows around the signal row space.At ζ = 1, the best rank-100 approximation is poor because the spectrum is noise-dominated.
- Connections to item-frequency methods: Frequent-Items uses O(1/ε) memory and O(1) update time, whereas Frequent-Directions uses O(m/ε) memory and O(m/ε) update time.The comparison motivates seeking a modified matrix algorithm with O(m) update time.