Approximate Sparse Recovery: Optimizing Time and Measurements

1. Introduction

• Sparse recovery models applications including data-stream heavy hitters, biological pooling, and sensor-network localization as identifying significant entries from linear measurements.The signal has k significant entries, and recovery focuses on their identities and values.Source: §1 · p. 1
• The design targets few measurements, sublinear decoding, and encoding and update times within constant or logarithmic factors of optimal.The algorithm randomizes the measurement matrix and guarantees recovery with high probability for each signal.Source: §1 · p. 2
• Previous sublinear methods use bit testers and hashing to isolate and estimate heavy hitters, while prior sublinear algorithms used extra log(N) measurement factors beyond the lower bound.The paper builds on the Count Sketch design and introduces a different measurement and coding strategy.Source: §1 · pp. 2–3
• The scheme uses O(k log(N/k)) measurements and runs in O(k log^c(N)) time, achieving ∥x − bx∥2 ≤ 2∥ν1∥2 with probability 3/4.Source: §1 · p. 2
• For the epsilon-parameterized system, runtime is O((k/epsilon) log^c(N)) and the measurement matrix has O((k/epsilon) log(N/k)) rows.The guarantee succeeds with probability 3/4.Source: §1 · p. 3
• With arbitrary measurement noise, the error dependence is suboptimal by log(k), but log(k) more measurements restore optimality.The paper notes that this robustness is important for physical measurement systems and less critical for digital stream monitoring.Source: §1 · p. 3
• The algorithm assigns positions to O(k) measurements, encodes a reduced O(N/k) domain with an error-correcting code, and tightens error and failure guarantees across iterations.As undiscovered heavy hitters decrease, later iterations can use more measurements to meet stricter guarantees.Source: §1 · p. 3

2.1. Vectors.

• The best k-term representation x_k is the signal formed from the j largest-magnitude terms in x; signal energy is the sum of squared entry magnitudes.The notation x_k can also denote the usual kth component of x, depending on context.Source: §2.1 · p. 3

2.2. Matrices.

• The measurement-matrix construction uses combinations of constituent matrices, summarized by operations whose results generally have N columns.The semi-direct product ⋉_r is the stated exception to the N-column rule for the input matrices.Source: §2.2 · p. 4, Figure 2 · p. 4

3.1. Measurement matrix.

• The overall matrix Φ applies a random permutation to the row direct sum of lg(k) iteration-specific matrices Φ(j), each used in a separate decoding iteration.Each Φ(j) combines an identification matrix D(j) and an estimation matrix E(j) by row direct sum.Source: §3.1 · p. 4
• At iteration j, the identification matrix D(j) is built from O(j) independent repetitions of a distribution combining a Bernoulli matrix, an error-correcting code, and sign flips.The code encodes position information in Θ(log log N)-bit blocks and corrects a constant fraction of errors; the code may be nonlinear.Source: §3.1 · pp. 4–5
• The estimation matrix E(j) uses O(j) independent repetitions of Bernoulli and sign-flip matrices, omitting the error-correcting code used for identification.The estimation construction is described as similar to identification, with different row-count constants.Source: §3.1 · p. 5

3.2. Measurements.

• Each iteration uses Φ(j)x, splitting measurements into w(j)=D(j)x for identification and z(j)=E(j)x for estimation; w(j) further separates code-related measurements.There are O(j) independent repetitions of the components at iteration j.Source: §3.2 · p. 5

3.3. Decoding.

• The decoding algorithm is presented in Figure 3 in the Appendix.Source: §3.3 · p. 5

4.1. Correctness.

• With probability 3/4, the algorithm runs in time k log^c N and uses a matrix with O(k log(N/k)) rows.Source: §4.1 · p. 6
• The identification step combines hashing with an error-correcting code and repeated magnitude estimates, allowing recovery despite individual measurements that fail with constant probability.The code uses Θ(log log N) parallel repetitions and median decoding for magnitude estimates.Source: §4.1 · pp. 7–8
• For measurement noise ν2, the error dependence is suboptimal by a factor log(k), improvable to log^(1/2+o(1)) k.Source: §4.1 · p. 9

4.2.1. Number of Measurements.

• O(k log(N/k)) measurements suffice overall because the per-iteration costs sum to a geometric sequence with ratio below 1.Source: §4.2.1 · p. 9

4.2.2. Encoding and Update Time.

• The original encoding uses log^2(k) log(N/k) nonzeros per matrix column, suboptimal by factor log^2(k); choosing failure probability 1/j^2 instead reduces this to log(k) log log(k) log(N/k) per column.Under this alternative, the ν2 contribution to noise equals log(k) log log(k) ∥ν2∥2.Source: §4.2.2 · p. 9

4.2.3. Decoding Time.

• Because the error-correcting code has length O(log log N), finding, encoding, and decoding it can be done in polylogarithmic time; the remaining decoding runtime is straightforward.Source: §4.2.2 · p. 9, §4.2.3 · p. 9

• The constructed system has near-optimal recovery time, meets the measurement lower bound, and places encode time, update time, and column sparsity within logarithmic factors of their lower bounds.Source: §5 · p. 10
• The authors conjecture that modifying the measurement-matrix distribution could extend the result to an ℓ1 ≤ Cℓ1 error guarantee.Source: §5 · p. 10
• The authors do not expect this approach to extend to the “for all” signal model, where current sublinear algorithms use at least O(log N) extra measurements.Source: §5 · p. 10
• Designing a sublinear-time recovery algorithm with an optimal number of rows for the “for all” model remains open.Source: §5 · p. 10

• A row direct sum vertically concatenates matrices, while an element-wise product multiplies corresponding entries of equal-sized matrices.Source: §6 · p. 10
• A semi-direct product replaces each nonzero in a row of one matrix with a column of the second matrix, applying that matrix to the selected vector entries.For a 0/1 row, the construction selects a subset of the input, removes unselected positions, then multiplies the resulting vector by the second matrix.Source: §6 · pp. 10–11
• Figure 3 gives pseudocode for the overall decoding algorithm.Source: Figure 3 · p. 12