Optimal Principal Component Analysis in Distributed and Streaming Models

Christos Boutsidis; David P. Woodruff; Peilin Zhong

Source-linked AI summary

Optimal Principal Component Analysis in Distributed and Streaming Models

Christos Boutsidis, David P. Woodruff, Peilin Zhong

arXiv:1504.06729v4Apr 25, 2015cs.DS

TL;DR

Distributed PCA seeks to reduce communication while preserving a rank-k approximation, and streaming PCA seeks such an approximation with limited space. This paper gives improved algorithms and bounds for these settings, including an O(skm + s · poly(kε−1))-word protocol in the arbitrary-partition model.

Problem
Distributed PCA communication is costly, and the best stated arbitrary-partition upper bound has an O(skmε−1) leading term, motivating protocols with better dependence on ε.
Source: §1 · p. 2, §1.1 · p. 2
Method
The paper develops distributed PCA protocols, including one for column-partitioned matrices with per-column sparsity, and uses smoothing or affine embeddings to address word-bounded communication.
Source: §1.1 · p. 3, §1.2.1 · pp. 5–6, §6 · p. 24
Results
The arbitrary-partition protocol uses O(skm + s · poly(kε−1)) words, while a column-partition lower bound is Ω(skm log(skm)) bits.
Source: §1.1 · p. 3
Takeaways & Limitations
The sparse column-subset protocol outputs O(k/ε) columns that can remain sparse when A is sparse and may improve interpretability.
Source: §1.1 · p. 3
The sparse-protocol bounds rely on sparsity in each column; overall sparsity alone does not bypass the Ω(skm) lower bound in the stated hard instance.
Source: §1.1 · p. 4

Abstract

from arXiv · show

We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix $A \in R^{m \times n},$ a rank parameter $k < rank(A)$, and an accuracy parameter $0 < \epsilon < 1$, we want to output an $m \times k$ orthonormal matrix $U$ for which $$ || A - U U^T A ||_F^2 \le \left(1 + \epsilon \right) \cdot || A - A_k||_F^2, $$ where $A_k \in R^{m \times n}$ is the best rank-$k$ approximation to $A$. This paper provides improved algorithms for distributed PCA and streaming PCA.

1 Introduction

This section introduces communication-efficient PCA in distributed and streaming models, including algorithms and lower bounds, with results addressing sparse inputs and streaming space. It also outlines the progression from prior work and linear-algebra preliminaries through PCA methods to communication lower bounds.

1 Introduction

Distributed PCA is challenging because communication is the bottleneck in systems such as Hadoop and Spark, and the goal is a shared low-dimensional subspace for downstream use.The approximation objective bounds projection error by (1 + ε) times the best rank-k residual; the coordinator model has each machine communicate with a coordinator rather than with other machines.Source: §1 · p. 2

1.1 Our Results

O(skm + s·poly(kε^-1)) words suffice for distributed (1 + ε)-approximate PCA, while the column-partition model requires Ω(skm log(skm)) bits under the stated conditions.The upper-bound algorithm gives each machine the same orthonormal matrix with arbitrarily large constant probability; the lower bound applies for positive constant C ≤ O(poly(skm)).Source: §1.1 · p. 3
For φ-sparse column-partitioned inputs, the protocol returns O(k/ε) columns supporting a (1 + ε)-approximation, and the stated lower bound is Ω(skφ log(skφ)) bits.The protocol’s column subset selection output is shared across machines; the sparsity condition bounds each column by φ nonzeros.Source: §1.1 · p. 3
A one-pass turnstile-streaming algorithm uses O(mk/ε + poly(k/ε)) words for (1 + ε)-approximate PCA, matching the cited one-pass bit lower bound up to words-versus-bits and a lower-order term.Unlike the prior algorithms [41, 31], it applies to the stronger turnstile model rather than only the column-update model.Source: §1.1 · p. 4
A modified one-pass algorithm outputs a (1 + ε)-approximate rank-k factorization in O((n + m)k/ε + poly(k/ε)) words, and a two-pass algorithm uses O(km + poly(k/ε)) words.The factorization space improves the cited upper bound and matches its cited lower bound up to the lower-order term; the two-pass space is stated to be optimal up to that term and words-versus-bits.Source: §1.1 · pp. 4–5

1.2.1 Upper Bounds

The upper-bound techniques combine sketching and smoothing for arbitrary partitions, distributed column sampling for sparse inputs, and sketch-based optimization for streaming.For arbitrary partitions, smoothing uses small Bernoulli noise when rank(A) is at least 2k and entries fit one machine word; below rank 2k, the method uses a Vandermonde-based basis and affine embeddings. Sparse-input sampling yields distributed column subset selection, while the streaming approach maintains sketches to avoid storing A.Source: §1.2.1 · pp. 5–7

1.2.2 Lower Bounds

The lower bounds establish Ω(skφ/ε) words for sparse distributed column subset selection and Ω(skm) words for dense column-partitioned PCA instances.The sparse argument uses a net of discretized orthonormal matrices; the dense lower bound holds even when machines output only projections of their local inputs onto the shared subspace.Source: §1.2.2 · p. 8

1.3 Road Map

The paper covers arbitrary-matrix distributed PCA, a modified version with machine-word-bounded communication, streaming PCA, sparse-matrix distributed algorithms including a faster variant, and communication lower bounds.The arbitrary-matrix algorithm’s communication is stated in real numbers; the modified algorithm bounds it in machine words.Source: §1.3 · p. 8

2 Outline of our result in the arbitrary partition model

The paper outlines distributed PCA for arbitrary partitions, using sketches to reduce the matrix before computing a low-rank approximation. This approach is developed as a batch method and then implemented in the distributed setting.

2 Outline of our result in the arbitrary partition model

The algorithm reduces both matrix dimensions in one round, computes an approximation from a small almost-square matrix, and achieves O(msk) words plus low-order terms.The stated lower bound is Ω(msk) bits [37].Source: §2 · pp. 8–9

2.1 Projection-cost preserving sketching matrices

Projection-cost preserving sketches preserve, up to error, the Frobenius-norm difference between a matrix and its projection, allowing a good rank-k projection of the sketch to approximate the original matrix.A dense Johnson-Lindenstrauss construction with ξ = O(kε^-2) has this property with probability at least 0.99.Source: §2.1 · p. 9

2.2 A batch algorithm for the fast low rank approximation of matrices

The batch method applies two dense Johnson-Lindenstrauss matrices to reduce both dimensions, then computes an SVD of the reduced matrix to construct a rank-k subspace.The method is presented as an efficient low-rank approximation technique for later distributed and streaming implementations.Source: §2.2 · p. 10

2.3 The distributed PCA algorithm

The distributed protocol has machines sketch their local matrices, sends the reduced data to a server for an SVD, and combines local products to form the output subspace.The remaining challenge identified here is obtaining small bit complexity, since the protocol could have very large bit complexity.Source: §2.3 · p. 11

3 Related Work

Prior distributed PCA work spans numerical linear algebra, heuristic machine-learning approaches, and theoretical algorithms. The theoretical literature includes column-partition methods and arbitrary-partition methods, with communication bounds and bit-complexity issues varying across approaches.

Related work

Numerical linear algebra work parallelizes standard SVD algorithms for high accuracy and low communication, often in models beyond the two partition models studied here.The paper points to ScaLAPACK and Elemental as distributed SVD software.Source: §3 · p. 16
Machine-learning and data-mining approaches target very large matrices but are typically heuristic and lack rigorous theoretical analysis.Source: §3 · p. 16
Column-partition theoretical methods achieve (1+ε) Frobenius-error approximations with O(skmε^-1) real-number communication, while word or bit bounds remained unexplored.The arbitrary-partition approach of Kannan, Vempala, and Woodruff is also introduced in this discussion.Source: §3 · p. 16
Other approaches include sampling-based spectral-norm approximation, whose cost can be prohibitive for large n and depends on the condition number, and orthogonal iteration for graph eigenvectors in a different model.The sampling algorithm also requires knowing ||A − A_k||_F.Source: §3 · p. 16

4 Preliminaries

The preliminaries define distributed and streaming PCA tasks, their computation models, and the approximation objective. They also give procedures for finding a best rank-k approximation constrained to a specified column or row subspace.

4 Preliminaries

Distributed PCA seeks a shared orthonormal m×k matrix whose projection achieves at most (1+ε) times the best rank-k Frobenius error while minimizing communication.The definitions distinguish arbitrary-partition and column-partition models.Source: §4 · p. 17
Distributed column subset selection seeks selected input columns that give a (1+ε)-relative Frobenius approximation while minimizing both the number of columns and communication.A rank-k subspace version additionally requires the output U to lie in the span of the selected columns.Source: §4 · p. 17
In the streaming model, a single pass processes entry updates and retains a sketch; streaming PCA then outputs an orthonormal rank-k matrix using only that sketch.The stated space cost includes all information stored during the stream.Source: §4 · p. 18

4.1 The best rank k matrix Πξ V,k(A) within a subspace V

For a prescribed column or row subspace, the procedures reduce the problem to an SVD in an orthonormalized subspace and return a best rank-k approximation within that span.The text gives corresponding column- and row-subspace procedures and their approximation lemmas.Source: §4.1 · pp. 19–20

5 Distributed PCA in the arbitrary partition model

The section develops a distributed PCA method based on projection-cost preserving sketches that reduce both dimensions of the input. Its arbitrary-partition implementation has a stated communication bound in real numbers, while the section identifies a word-size issue for one broadcast.

5 Distributed PCA in the arbitrary partition model

The method reduces both matrix dimensions in the same round and computes an approximate SVD from a small almost-square matrix, unlike prior approaches described as reducing one dimension.The section presents this as a communication-optimal algorithm in the arbitrary-partition model, with O(msk) words plus low-order terms.Source: §5 · p. 20

5.1 Projection-cost preserving sketching matrices

A projection-cost preserving sketch maintains projection costs up to error, and a good rank-k projection of the sketch yields a good rank-k approximation to the original matrix.A dense Johnson-Lindenstrauss construction with ξ = O(kε^-2) is reported to have the sketch property with probability at least 0.99.Source: §5.1 · p. 21

5.2 A batch algorithm for the fast low rank approximation of matrices

The batch algorithm uses dense Johnson-Lindenstrauss matrices to reduce both dimensions before computing an SVD of the reduced matrix.It is presented as an efficient low-rank approximation technique that can be implemented in distributed and streaming settings.Source: §5.2 · pp. 21–22

5.3 The distributed PCA algorithm

The distributed implementation has machines sketch their local inputs, the server compute the reduced SVD, and machines send products used to construct the final subspace.Source: §5.3 · p. 23

5.3.1 Main result

O(msk + s·poly(k/ε)) real numbers are communicated, but the stated bound does not yet count words because the server broadcasts a matrix whose entries could be unbounded.The section says the following section resolves this word-length issue.Source: §5.3.1 · p. 24

6 Obtaining bit complexity for the distributed PCA algorithm

This section establishes bit complexity for the distributed PCA algorithm by developing and analyzing a word-bounded protocol for the cases rank(A) le 2k and rank(A) > 2k. For the higher-rank case, it relates the perturbed matrix’s residual to that of A to complete the approximation guarantee.

6.1 Testing the rank of a distributed matrix

The rank test distinguishes rank(A) ≤ 2k using O(sk^2) words and succeeds with probability 1 − δ.The coordinator distributes random row identities, machines return small matrix sketches, and the coordinator tests the rank of their sum.Source: §6.1 · pp. 24–25

6.2.1 Subsampled Randomized Hadamard Transform and Affine Embeddings

An SRHT is used for fast dimension reduction, and the affine-embedding lemma gives a simultaneous guarantee when its row count is ξ = O(r/ε^2).The section also states that SRHT matrix-vector multiplication can be computed in at most 2m log^2(ξ + 1) operations.Source: §6.2.1 · p. 25

6.2.2 Generalized rank-constrained matrix approximations

The generalized rank-constrained approximation subsection characterizes the minimum-Frobenius-norm feasible solution among matrices of rank at most k.It presents this solution as a formula for the stated optimization problem.Source: §6.2.2 · p. 26

6.2.3 The PCA protocol

When rank(A) ≤ 2k, a distributed PCA protocol achieves O(smk + sk^2/ε^2) words of communication with failure probability at most δ.It uses a sampled matrix to recover A’s column space, then affine embeddings to form a shared rank-constrained approximation.Source: §6.2.3 · p. 26

6.3.1 Lower bounds on singular values of matrices with integers entries

For integer matrices with bounded entries, the section gives a lower bound on the k-th singular value and shows that a small random perturbation of a rectangular matrix has smallest singular value at least 1/n^B with high probability.The rectangular perturbation uses independent entries equal to ±1/n^D with equal probability.Source: §6.3.1 · p. 27, §6.3.2 · p. 28

6.4 Description of algorithm

For rank(A) > 2k, the algorithm perturbs one machine’s input with independent ±1/n^D noise, sketches the matrices, rounds a communicated matrix, and recovers a rank-k output basis.The perturbation yields B = A + N_m,n; the protocol then uses Johnson–Lindenstrauss matrices and sends a rounded sketch before reconstructing the output.Source: §6.4 · pp. 28–29

6.5 Main result

The final algorithm communicates O(msk + s·poly(k/ε)) words, with each word using O(log(mnsk/ε)) bits.Theorem 43 states that its output has k orthonormal columns with arbitrarily large constant probability.Source: §6 · p. 24, §6.5 · p. 29

6.7 Proof of Eqn. 6 if rank(A) > 2k

For the rank(A) > 2k analysis, subspace embeddings bound the pseudoinverse norm, and the argument bounds the error on the perturbed matrix by (1 + O(ε)) times its best rank-k error.The proof relates this bound to the original matrix through the perturbation and the Frobenius-norm triangle inequality.Source: §6.7 · pp. 30–31
After bounding the candidate’s error for B while controlling perturbation terms, the proof applies Lemma 47 in Eqn. (7), squares the inequality, and rescales ε to conclude.The comparison uses that the noise matrix can be made arbitrarily small and that the residual for B is related to the residual for A.Source: §6.7 · pp. 31–32
Weyl’s inequality and bounds on the perturbation yield ||B − B_k||_F ≤ (1 + 2ε)||A − A_k||_F.The noise terms are controlled using Corollary 39 and can be made sufficiently small relative to the residual.Source: §6.7 · pp. 31–32

7 Streaming Principal Component Analysis

This section develops streaming PCA algorithms for turnstile streams of matrix-entry updates, covering one-pass and two-pass protocols, including a method with bit-space complexity. It also analyzes a two-pass protocol for rank(A) > 2k in terms of approximation error, space, and running time.

7.1.1 The algorithm which outputs U

With probability 0.96, the algorithm gives a matrix U with k orthonormal columns, meets the space lower bound in, and uses O(poly(kε^-1)) time per update.Source: §7 · p. 32, §7.1.1 · p. 35

7.1.2 A variation which outputs A∗

A slight modification of the Section 7.1.1 algorithm outputs a matrix A*; its sketch matrices M, L, N, and D use the same total space, while maintaining C requires additional O(nkε−1) space.Source: §7.1.2 · pp. 35–36

7.2 Two-pass streaming PCA with “real numbers” space complexity

In two passes, a batch-algorithm variant achieves the PCA guarantee with O(mk) + poly(k/ε) real-number space, but its space bound is only in real numbers.The theorem states the guarantee holds with probability 0.98.Source: §7.2 · p. 37

7.3 Two-pass streaming PCA with bit space complexity

The bit-space method runs the rank test alongside both PCA protocols in the first pass, then follows the selected protocol in the second pass to avoid a third pass.It branches on whether rank(A) < 2k or rank(A) ≥ 2k; the section presents this as an optimal two-pass algorithm.Source: §7 · p. 32, §7.3 · p. 38

7.3.1 Streaming PCA protocol when rank(A) ≤2k

For rank(A) ≤ 2k, the two-pass protocol implements the distributed PCA method using an n × 2k matrix and affine embeddings of dimension O(k/ε²).The first pass maintains a sketch using H′′; the second pass maintains sketches with the affine embeddings.Source: §7.3.1 · p. 38

7.3.2 Streaming PCA protocol when rank(A) > 2k

The idea is to implement a streaming version of step 3 of the algorithm in Section 6.4, constructing dense Johnson-Lindenstrauss matrices S ∈ R^(ξ1×m) and T ∈ R^(n×ξ2), with ξ1 = O(kε−2) and ξ2 = O(kε−2).Source: §7.3.2 · p. 39
The rank(A) > 2k protocol sketches the stream in a first pass, computes and rounds a rank-k SVD, then uses a second pass to form X and output a basis for span(X).The final matrix X has rank at most k.Source: §7.3.2 · p. 39

7.3.3 Main result

With arbitrarily large constant probability, the output has k orthonormal columns and meets the theorem’s approximation guarantee; each update takes O(poly(kε^-1)).Computing the final output basis adds O(mk^2) running time.Source: §7.3.3 · p. 39

8 Distributed PCA for sparse matrices in column-partition model

The section presents distributed PCA for column-partitioned sparse matrices: it samples a small set of input columns, then finds a rank-k approximation within their span. Its sampling combines local, global, and adaptive stages.

8 Distributed PCA for sparse matrices in column-partition model

The algorithm first selects O(k/ε) columns from A, then finds an orthonormal rank-k matrix U in their span.The three-stage procedure uses local sampling, server-side down-sampling, and adaptive sampling from the entire matrix.Source: §8 · p. 40

8.1.1 Column sampling algorithms

Local sampling uses [24], global down-sampling uses, and adaptive sampling uses to select additional columns.The section also describes these as BSS-based sampling, deterministic column selection, and residual-based adaptive sampling, respectively.Source: §8.1.1 · p. 40, §8 · p. 40

8.1.2 Distributed adaptive sampling

Distributed adaptive sampling coordinates local residual information so the server can sample columns across the partitioned matrix.The coordinator sends the current column set C to the machines, which compute local residual norms and report values used to determine sampling probabilities.Source: §8.1.2 · pp. 42–43

8.1.3 Low-rank matrix approximations within a subspace

Within the selected subspace, a sketch of Y^T A supplies the top-k left singular vectors used to form U.The stated procedure has probability at least 1 − e^−c of achieving its error guarantee and takes O(mnξ) time.Source: §8.1.3 · pp. 43–44

8.2 Detailed description of the algorithm

The detailed algorithm sends sampled columns to the server, performs adaptive sampling, and distributes the resulting subspace for computing U.Machines use the shared subspace and sketch to compute the same rank-k output.Source: §8.2 · pp. 44–45

8.3 Main Result

The section states the approximation and resource analysis for the sparse column-partition algorithm. Its total communication bound is O(skφ/ε + sk²/ε⁴) words.

8.3 Main Result

The main result analyzes approximation error, communication, and running time for the algorithm.The supplied theorem passages state guarantees for the sampled columns and the orthonormal rank-k output, but do not include the full bounds.Source: §8.3 · p. 45

8.4.1 Proof of Eqn. 10

The proof establishes that G is a (4k, 1/2)-projection-cost preserving sketch of A.The argument uses local sketches and a union bound.Source: §8.4.1 · p. 46

8.4.3 Running time

The running-time analysis separates local column sampling, global column sampling, adaptive sampling, and rank-k approximation within the sampled span.The supplied passages give stage costs, including O(nnz(A) log(ms) + m · poly(k, ε, log(s))) for local column sampling.Source: §8.4.3 · p. 48

8.4.4 Communication Complexity

O(skφ/ε + sk²/ε⁴) words is the algorithm’s total communication complexity.The stated setting assumes each column has at most φ nonzero entries.Source: §8.4.4 · pp. 48–49

9 Faster Distributed PCA for sparse matrices

The section modifies the distributed PCA algorithm to reduce running time by replacing selected steps with procedures whose time is proportional to the nonzero entries of the underlying matrices, at a slight increase in communication.

9 Faster Distributed PCA for sparse matrices

Selected algorithm steps are replaced with nearly as accurate procedures that run in time proportional to the underlying matrices’ nonzero entries, with a slight communication increase.The modifications target steps 2-(a), 3-(a), and 4-(b); the analysis does not optimize constants.Source: §9 · p. 49

9.1 Background material

The background section introduces sparse subspace embeddings and randomized sparse SVD, then describes higher-probability and input-sparsity-time variants of the sampling and subspace approximation procedures.

9.1.1 Constant probability sparse subspace embeddings and sparse SVD

A sparse subspace embedding can be applied in input-sparsity time and, with probability at least 0.99, preserves squared norms within a factor of 1 + ε.The stated embedding dimension is ξ = Ω(ρ²ε⁻²), and nnz(AW^T) ≤ nnz(A).Source: §9.1.1 · p. 49

9.1.2 High probability sparse SVD

The sparse SVD procedure is extended to achieve probability at least 1 − δ − 1/n for its stated approximation guarantee.The section motivates boosting because constant failure probability across s local runs can yield overall failure probability of order O(s).Source: §9.1.2 · p. 50

9.1.3 Fast column sampling techniques

Fast column-sampling procedures use sparse embeddings and input-sparsity-time analogues of sampling methods, with high-probability bounds for one procedure.The section describes selecting among repeated candidates using singular-value and Frobenius-norm criteria.Source: §9.1.3 · pp. 51–52

9.1.4 Fast Low-rank matrix approximations within a subspace

The fast within-subspace approximation uses a sparse subspace embedding to sketch Y^T A before extracting the top-k left singular vectors.The stated computation time is O(nnz(A) + mcξ), with probability at least 0.99.Source: §9.1.4 · p. 53

9.2 Detailed description of the algorithm

The algorithm builds a column subset through local and global sampling, then adaptively samples residual columns. It uses the resulting span to compute a rank-k approximation shared across machines.

Local Column Sampling

Local sampling selects O(k) columns from each machine’s matrix, which are sent to the server.Each machine forms C_i=A_iS_i using BssSamplingI(A_i, 4k, 1/2, 0.01/s).Source: §9.2 · p. 54

Global Column Sampling

The server combines the locally selected columns into G and chooses 4k columns from G to form C.The chosen columns are obtained with DeterministicCssFrobeniusSparse(G, k, c1).Source: §9.2 · p. 54

Adaptive Column Sampling

Adaptive sampling uses residuals after projection onto C to select additional columns for ˜C.Machines compute residual sketches ˜Ψ_i and send sampling weights; the server samples machines, which return locally sampled columns.Source: §9.2 · pp. 54–55

Rank-k matrix in the span of ˜C

The machines compute a shared rank-k matrix U in the span of ˜C using a subspace embedding and the top k left singular vectors.They factor ˜C=YR, combine sketched products, and form U=Y∆.Source: §9.2 · p. 54

9.3 Main result

Theorem 74 analyzes the approximation error, communication complexity, and running time of the algorithm. Its statements cover both the selected column matrix ˜C and the resulting orthonormal matrix U.

9.3 Main result

The theorem analyzes the algorithm’s approximation error, communication complexity, and running time.The supplied theorem statements concern both ˜C and U.Source: §9.3 · p. 55
The theorem includes an approximation guarantee for a matrix ˜C containing O(k/ε) columns of A.The supplied statement gives a probability qualifier but does not include the complete bound.Source: §9.3 · p. 55
The theorem also states a result for an m × k matrix U with k orthonormal columns.The supplied statement is truncated before its full guarantee.Source: §9.3 · p. 55

9.4 Proof of Theorem 74

The proof connects the algorithm’s sampled columns to approximation guarantees, then establishes the final U guarantee. The section also reports running-time and communication costs.

9.4.1 Proof of Eqn. 15

Projection-cost preservation for G, the rank of C, and best-rank-k properties support the inequalities used to establish Equation 15.The proof also invokes Lemma 71 and concludes by combining the bound with Equation 17.Source: §9.4.1 · pp. 55–56

9.4.2 Proof of Eqn. 16

The proof applies Lemma 73 to U after establishing the guarantee for ˜C, then uses a union bound to conclude Equation 16.Source: §9.4.2 · p. 56

9.4.3 Running time

The running-time analysis lists costs for local sampling, adaptive sampling, and finding the rank-k matrix in the span of ˜C.The listed expressions include O(nnz(A) log(ms) + m · poly(k, ε, log(s))) for local sampling and O(nnz(A) · log n + m · s · poly(k, ε−1, log n)) for adaptive sampling.Source: §9.4.3 · pp. 56–57

9.4.4 Communication Complexity

The algorithm’s total communication complexity is O(skφ/ε + sk³/ε⁵) words.Source: §9.4.4 · p. 57

10.1 Dependence on Ω(ε−2) bits for distributed PCA in arbitrary partition model

The lower-bound argument reduces Gap Hamming Distance to distributed PCA. If the server computes U, the machines can distinguish the promised cases, so computing U incurs communication.

10.1 Dependence on Ω(ε−2) bits for distributed PCA in arbitrary partition model

The proof identifies Gap Hamming Distance as the source of the reduction and cites an Ω(n)-bit communication requirement for its stated promise problem.The cited promise distinguishes inputs at Hamming distance below n/2 − c√n from the other case.Source: §10.1 · p. 58
The reduction encodes the two promised inner-product cases in matrices and has the server compute U for both machines.The promise is xTy < −2/ε or xTy > 2/ε.Source: §10.1 · p. 58
The resulting U lets the machines distinguish the two cases, making its computation the communication cost of the reduction.The passage relates this cost to the Ω(1/ε²)-bit lower bound for Gap Hamming Distance.Source: §10.1 · p. 59

10.2 Lower bounds for distributed PCA on dense matrices

The section establishes communication lower bounds for distributed PCA by constructing hard matrices whose planted subspace can be recovered from a sufficiently accurate PCA output. For dense inputs, this yields an Ω(skm) word lower bound under the stated rank and approximation conditions.

10.2.1 Preliminaries

Theorem 77 supplies a finite net of projection matrices with disjoint operator-norm δ-balls, and the hard instance is built from a member of that net.The net size is stated as 2^Ω(k(m−k) log(1/δ)).Source: §10.2.1 · p. 60

10.2.2 Hard instance construction

The construction sets δ = 1/(skm), rounds a random net member’s orthonormal basis entries to multiples of 1/B, and places scaled identity blocks and zero padding on the other servers.The column-partition setting assumes n ≥ sm.Source: §10.2.2 · p. 60

10.2.3 Intermediate results

If n < sm, choosing s′ with n−m ≤ s′m ≤ n yields an Ω(s′mk) lower bound, which is Ω(n) when n ≥ 2d.Source: §10.2.3 · p. 60
The rank-k span of A1 gives an upper bound on the best rank-k residual, with the remaining scaled identity blocks contributing at most (s−2)m/B².The argument uses that the other blocks are annihilated by projection onto A1’s column span.Source: §10.2.3 · p. 61

10.2.4 Main Argument

A sufficiently accurate output projector identifies the planted subspace: the protocol can deterministically recover the construction matrix R from A and a rank-at-most-k projector Q.The net’s separated neighborhoods let each machine identify the unique net member associated with Q.Source: §10.2.4 · pp. 61–62
Ω(skm log(skm)) bits, or Ω(skm) words, are required when n = Ω(sm), k ≤ 0.99m, and 1 < C < poly(skm).The protocol must succeed with probability at least 2/3; the input entries may be bounded integer multiples of 1/B for B = poly(skm).Source: §10.2.4 · pp. 62–63

10.3 Lower bounds for distributed PCA on sparse matrices

The dense-matrix PCA lower bound extends to sparse matrices by embedding the hard instance in the top rows and padding the rest with zeros. Under the stated conditions, the resulting communication cost scales with the number of rows containing the hard instance.

10.3 Lower bounds for distributed PCA on sparse matrices

Padding the φ-row hard instance with m−φ zero rows preserves its column partition and transfers the lower bound to matrices with m rows.Source: §10.3 · p. 63
Any protocol succeeding with probability at least 2/3 in having server i output a rank-at-most-k projector approximation with Frobenius error at most C times the best rank-k error requires Ω(skφ log(skφ)) communication bits.At word size Θ(log(skφ)) bits, this is an Ω(skφ) word lower bound.Source: §10.3 · p. 64
An algorithm succeeding with probability at least 2/3 in having every i-th server output Qhat Ahat_i, where Qhat is a rank-at-most-k projector and ||Ahat − Qhat Ahat||F ≤ C||Ahat − Ahat_k||F, requires Ω(skφ log(skφ)) communication bits.Source: §10.3 · p. 64

10.4 Lower bounds for distributed column-based matrix reconstruction

The section derives distributed column-subset-selection lower bounds from discretized hard instances and limited sharing among rounded orthonormal matrices. It obtains a communication lower bound that grows with the number of servers, sparsity parameter, rank, and 1/ε.

10.4.1 A Net of discretized Deshpande-Vempala hard instances

Rounding an orthonormal matrix’s entries to multiples of M preserves a lower bound against projections onto subsets of at most k/(6ε) columns.Source: §10.4.1 · p. 64
For the block-diagonal Deshpande–Vempala instance, any (1+ε)-approximation using a subset of columns requires more than k/(2ε) selected columns.The construction uses k diagonal blocks of a matrix whose i-th column is e1 + ei+1.Source: §10.4.1 · pp. 64–65

10.4.2 Column sharing of discretized orthonormal matrices

Two independently sampled orthogonal matrices have probability at most e^−Θ(nr log M) of sharing r rounded columns under the stated small-M condition.Source: §10.4.2 · p. 66
The k-fold extension bounds the probability of prescribed column sharing across k independent matrix pairs by e^−Θ(nΣr_z log M), yielding a large family with separated sharing patterns.The family has size e^Θ(nt log M) under the corollary’s conditions.Source: §10.4.2 · p. 67

10.4.3 Hard instance construction

The sparse hard instance places k blocks in the first kφ rows, uses a discretized net member in its construction, and has at most φ nonzero entries per column.Its construction ensures that no k/(2ε) columns span a k-dimensional subspace giving a (1+ε)-approximation.Source: §10.4.3 · p. 67

10.4.4 Main theorem

Ω(sφk(log(mn))/ε) bits, or Ω(sφk/ε) words, are required when 2/ε ≤ φ and kφ ≤ min(m,n), even for columns with at most φ bounded, discretized nonzeros.The protocol may be randomized and must succeed with probability at least 2/3.Source: §10.4.4 · pp. 68–69

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings2012