Source-linked AI summary
Circulant and Toeplitz matrices in compressed sensing
Holger Rauhut
TL;DR
Compressed sensing seeks sparse-vector recovery from few non-adaptive linear measurements, but prior guarantees for random circulant and Toeplitz matrices had pessimistic sparsity dependence. The paper studies arbitrary-row partial versions of these matrices and proves ℓ1-recovery with measurement count linear in sparsity up to logarithmic factors.
Problem
Prior recovery bounds for random Toeplitz and circulant matrices grew quadratically with sparsity, whereas linear scaling was expected.
Method
The paper analyzes ℓ1-minimization with random partial circulant or Toeplitz matrices formed from Bernoulli vectors and permits an arbitrary subset of rows.
Results
Ignoring logarithmic factors, the necessary number of measurements for recovery scales linearly with sparsity, specifically n ≥ Cs log^2(N).
Takeaways & Limitations
Partial random circulant and Toeplitz matrices provide recovery guarantees with substantially improved sparsity scaling over the earlier quadratic bound.
Abstract
from arXiv · showhide
Compressed sensing seeks to recover a sparse vector from a small number of linear and non-adaptive measurements. While most work so far focuses on Gaussian or Bernoulli random measurements we investigate the use of partial random circulant and Toeplitz matrices in connection with recovery by $\ell_1$-minization. In contrast to recent work in this direction we allow the use of an arbitrary subset of rows of a circulant and Toeplitz matrix. Our recovery result predicts that the necessary number of measurements to ensure sparse reconstruction by $\ell_1$-minimization with random partial circulant or Toeplitz matrices scales linearly in the sparsity up to a $\log$-factor in the ambient dimension. This represents a significant improvement over previous recovery results for such matrices. As a main tool for the proofs we use a new version of the non-commutative Khintchine inequality.
I. INTRODUCTION
The paper studies sparse-signal recovery using structured random measurement matrices, motivated by the computational and application advantages of circulant and Toeplitz matrices. It addresses pessimistic prior recovery bounds by establishing linear sparsity scaling for ℓ1-minimization.
- Circulant and Toeplitz matrices use fewer random numbers than Bernoulli or Gaussian matrices and support fast matrix-vector multiplication.They also arise naturally in applications such as identifying a linear time-invariant system.
- Basis Pursuit, or ℓ1-minimization, is a major approach for efficiently recovering sparse vectors.Modern optimization algorithms such as LARS are described as reasonably fast.
- Prior recovery estimates for random Toeplitz and circulant matrices required measurements growing quadratically with sparsity, despite expectations of linear scaling.The paper aims to close this theoretical gap with recovery guarantees that scale linearly in sparsity.
II. SPARSE RECOVERY WITH CIRCULANT AND TOEPLITZ
The paper formulates sparse recovery with arbitrary row subsets of random partial circulant and Toeplitz matrices and analyzes recovery by ℓ1-minimization. Its main result gives linear sparsity scaling up to logarithmic factors, while retaining random-sign assumptions on the signal coefficients.
- Problem formulation: Sparse recovery seeks an s-sparse vector x from underdetermined measurements y = Ax, but direct ℓ0-minimization is generally NP-hard.The paper therefore considers the convex ℓ1-minimization problem, whose solutions often coincide with the original sparse vector.
- Measurement matrices: Partial circulant and Toeplitz matrices are formed by selecting an arbitrary deterministic subset of n rows from structured matrices generated by Bernoulli ±1 vectors.The construction includes random vectors b and c with independent Bernoulli ±1 entries.
- Recovery guarantees: Earlier restricted-isometry bounds required n ≥ Cδs^2 log(N/s), reflecting pessimistic quadratic sparsity scaling.The paper also gives an alternative restricted-isometry estimate with n ≥ Cδ^-2s^2 log^2(N), while noting that this bound is probably non-optimal.
- Measurement matrices: The paper allows Ω to be any subset of {1, ..., N} with cardinality n, unlike earlier settings focused on particular row selections.A periodic or non-periodic convolution followed by downsampling is one structured case discussed in the paper.
- Recovery guarantees: The main recovery result ensures ℓ1-minimization recovery with n ≥ Cs log^2(N), so the measurement count is linear in sparsity up to logarithmic factors.The theorem assumes Bernoulli-generated matrices and random Bernoulli signs on the nonzero entries of x; the authors suggest the log exponent and sign assumption may be improvable.
III. PROOF OF THEOREM 2.1
The proof combines a recovery criterion for ℓ1-minimization with bounds on coherence and the inverse restricted Gram operator. These estimates yield high-probability recovery for random partial circulant and Toeplitz matrices.
- Recovery criterion: The Fuchs–Tropp recovery theorem reduces unique Basis Pursuit recovery to controlling the pseudoinverse of A_Λ and the coherence of A.The pseudoinverse is the Moore–Penrose pseudoinverse of A_Λ, while coherence is the largest absolute inner product between distinct columns.
- Matrix estimates: The coherence of random partial circulant and Toeplitz matrices is bounded with high probability using a proposition based on Rademacher-series estimates.The coherence proposition supplies one of the two controls needed by the recovery theorem.
- Matrix estimates: For a fixed support Λ, the smallest eigenvalue of A_Λ^*A_Λ is bounded below with high probability under the stated sampling condition.This lower bound controls the operator norm of the pseudoinverse appearing in the recovery criterion.
- Scope of the estimate: The argument applies to fixed support sets and random matrix coefficients, but it does not establish a uniform estimate over all supports for given coefficients.A union bound over all supports would produce an essentially worse estimate.
- Conclusion: Combining the estimates gives recovery by ℓ1-minimization with failure probability below 3ε under the theorem’s sampling conditions.The proof uses Hoeffding’s inequality and bounds the separate failure terms before combining them.
IV. NON-COMMUTATIVE KHINTCHINE INEQUALITIES
The paper develops non-commutative Khintchine tools for Bernoulli matrix series and extends them to second-order chaos variables. Decoupling and interpolation support the inequalities used in the coherence and eigenvalue proofs.
- Core inequality: The proofs of the coherence and eigenvalue estimates rely on versions of the non-commutative Khintchine inequality.The inequalities are formulated using Schatten class norms of matrices.
- Bernoulli extension: The Gaussian matrix inequality is transferred to independent Bernoulli ±1 variables through the contraction principle.This yields the Bernoulli form used for the random matrix coefficients.
- Second-order chaos: A second-order chaos extension bounds sums involving matrices A_j,k with vanishing diagonal blocks.Its proof combines decoupling with the Bernoulli non-commutative Khintchine inequality.
- Proof mechanism: The proof embeds the coefficient matrices into block matrices and evaluates the resulting Schatten norms through block products and repeated Khintchine estimates.The construction uses both the original blocks and versions with adjoint blocks interchanged.
- Constant and limitation: The scalar case removes the factor π/2 in the constant, but whether the same removal holds in the non-commutative setting remains unclear.Interpolation is used after repeating the proof in the scalar case.
V. PROOF OF THE COHERENCE ESTIMATE
The coherence proof represents column inner products of normalized partial circulant and Toeplitz matrices as random sums. Moment estimates from the scalar Khintchine inequality and a probability lemma then yield the coherence bound.
- Column inner products: Inner products between distinct normalized circulant columns are expressed through coefficient arrays indexed by the selected row set Ω.The analogous representation is constructed for Toeplitz columns using non-periodic index differences.
- Moment bounds: The coefficient arrays have squared magnitudes summing to |Ω| = n, enabling scalar Khintchine moment estimates for both matrix types.The same estimate is stated for the Toeplitz column inner products.
- Tail estimate: A probability lemma converts moment growth of the column inner products into tail bounds for their magnitudes.The lemma starts from an L^p bound of the form (E Z^p)^(1/p) ≤ αβ^(1/p)p^(1/γ).
- Coherence conclusion: A union bound over all pairs of distinct columns produces the high-probability coherence estimate.The moment parameter is chosen as u = log(2N^2/ε).
VI. PROOF OF THEOREM 3.4
The proof develops an operator-norm bound for XΛ by representing circulant and Toeplitz constructions through shift operators, restrictions, extensions, and projections. Applying trace estimates, Hölder-type bounds, Khintchine’s inequality, and Lemma 5.1 yields the stated probabilistic control and completes Theorem 3.4.
- Operator setup: The proof represents circulant and Toeplitz cases uniformly using shift operators, restriction operators, extension operators, and projections.The operator Dj is taken as either Sj or Tj, with sums indexed differently for circulant and Toeplitz matrices.
- Operator setup: The central quantity is XΛ := A∗ΛAΛ − IΛ, whose operator norm must be bounded.IΛ denotes the identity on RΛ, and R∗Λ extends vectors by zeros outside Λ.
- Norm estimates: Trace and non-negativity arguments produce successive estimates for the block matrices used in the norm bound.The proof introduces the block matrix F with diagonal blocks removed and repeatedly exploits non-negative entries and trace identities.
- Norm estimates: Khintchine’s inequality, Hölder’s inequality, and the geometric–arithmetic mean inequality are combined to control Schatten and operator norms.The argument applies Khintchine’s inequality after comparing the operator norm with Schatten norms, then combines the resulting estimates.
- Conclusion: With the optimal choice κ = 1, setting the bound equal to ǫ gives ∥XΛ∥ ≤ δ with probability at least 1 − ǫ under the stated condition.This probabilistic estimate is the final quantitative step before the proof concludes Theorem 3.4.