Prerequisites & Notation

Before You Begin

This chapter assumes familiarity with linear estimation (least squares, Tikhonov/ridge regularization) and basic convex analysis. Compressed sensing stands at the intersection of approximation theory, high-dimensional probability, and convex optimization; we will draw on all three.

  • Linear least squares and the normal equations(Review ch05)

    Self-check: Can you derive x^LS=(ATA)βˆ’1ATy\hat{\mathbf{x}}_{LS} = (\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^T\mathbf{y} and state when ATA\mathbf{A}^T\mathbf{A} is invertible?

  • Singular value decomposition and condition numbers(Review ch06)

    Self-check: Can you bound βˆ₯Axβˆ₯2\|\mathbf{A}\mathbf{x}\|_2 in terms of the singular values of A\mathbf{A}?

  • Tikhonov (ridge) regularization(Review ch09)

    Self-check: Can you explain why ridge regression shrinks coefficients but does not set them to zero?

  • Basic convex optimization: convex sets, convex functions, KKT conditions

    Self-check: Can you state the KKT conditions for a constrained minimization with linear equality constraints?

  • Gaussian concentration (Hoeffding, Bernstein) and random matrix basics

    Self-check: Can you state the concentration of Ο‡n2/n\chi^2_n / n around 11?

Notation for This Chapter

Symbols introduced in this chapter. In all that follows, A\mathbf{A} denotes the MΓ—NM \times N sensing (measurement) matrix with Mβ‰ͺNM \ll N. Vectors are column vectors; SβŠ†{1,…,N}\mathcal{S} \subseteq \{1,\ldots,N\} denotes the support of a sparse vector.

SymbolMeaningIntroduced
NNAmbient dimension (number of unknowns)s01
MMNumber of measurements, Mβ‰ͺNM \ll Ns01
ssSparsity level: number of nonzero entries in x\mathbf{x}s01
S=supp(x)\mathcal{S} = \mathrm{supp}(\mathbf{x})Support set: {i:xi≠0}\{i : x_i \neq 0\}s01
βˆ₯xβˆ₯0\|\mathbf{x}\|_0Number of nonzero entries (not a true norm)s01
A\mathbf{A}Sensing / measurement matrix of size MΓ—NM \times Ns01
w\mathbf{w}Noise vector, typically w∼N(0,Οƒ2I)\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \sigma^2\mathbf{I})s01
Ξ΄s\delta_sRestricted isometry constant of order sss03
ΞΌ(A)\mu(\mathbf{A})Mutual coherence of A\mathbf{A}s03
Ξ»\lambdaRegularization parameter for LASSO / BPDNs02
z^LASSO\hat{\mathbf{z}}_{\text{LASSO}}LASSO solution (sparse estimator)s02
Οƒs(x)1\sigma_s(\mathbf{x})_1Best ss-term approximation error in β„“1\ell_1: min⁑∣Tβˆ£β‰€sβˆ₯xβˆ’xTβˆ₯1\min_{|\mathcal{T}| \leq s} \|\mathbf{x} - \mathbf{x}_\mathcal{T}\|_1s04
← Ch 12The Sparse Recovery Problem