A mathematical introduction to compressive sensing
There are two important features of this book. The first feature is the set of ``Notes sections presented at the end of each chapter. These Notes supplement the relevant references, historical remarks, additional facts and open questions studied in the respective chapters. They can be used to expand the students' knowledge and understanding or as an opportunity to conduct a seminar. The second feature is the collection of exercises spread throughout the chapters, being an essential component for students to learn the presented stuff. Moreover, the book concludes with three appendices that cover basic material from matrix analysis, convex analysis, and other interesting topics that hint at advanced areas of mathematics. The book contains fifteen chapters. The first chapter gives a brief description of compressive sensing with some motivations, applications and a detailed overview of the book. In Chapter 2 the notions of vector sparsity and compressibility with some basic algorithms are given. Also, the minimal number of linear measurements required to recover sparse vectors is investigated in two different settings. Finally, it is proved that \(\ell_0\)-minimization, the ideal recovery scheme, is NP-hard in general. In Chapter 3 a popular algorithm used in compressive sensing is presented. This algorithm covers three methods: optimization methods, greedy methods, and thresholding-based methods. Chapter 4 is focussed on the basis pursuit (\(\ell_1\)-minimization) strategy, which consists in solving a convex optimization problem. Necessary and sufficient conditions for exact or approximate reconstruction of the original sparse or compressible vector are discussed. Also, the recovery of sparse vectors via basis pursuit is interpreted in terms of polytope geometry. In Chapter 5 the notion of coherence of a matrix and some of its generalizations are introduced. The authors investigate how small the coherence can be and they give some matrices with small coherence. Finally, they discuss some sufficient conditions expressed in terms of the coherence that guarantee the success of orthogonal matching pursuit, basis pursuit, and thresholding algorithms. In Chapter 6 the concept of restricted isometry property is introduced, which is known as a uniform uncertainty principle. The success of sparse recovery is established under some conditions on restricted isometry constants for basis pursuit, thresholding-based algorithms and for greedy algorithms. Chapter 7 deals with the basic facts of probability. The relation of moments of random variables to their tails and deviation inequalities for sums of independent random variables by means of moment-generating functions are studied. Chapter 8 incorporates the expectation of the \(\ell_p\)-norm of a standard Gaussian vector for \(p = 1,2,\infty\). Some simple results for Rademacher sums as well as the symmetrization method are presented. Decoupling inequalities are introduced to replace one sequence of random variables in a double sum by an independent copy. The scalar Bernstein inequality for bounded random variables is extended to a powerful deviation inequality for the operator norm of sums of random matrices. Finally, a deviation inequality for the supremum of an empirical process, which is sometimes called Talagrand's concentration inequality or Bousquet's inequality, is discussed. The sparse recovery based on random matrices and some related topics are discussed in Chapters 9--12. In Chapter 13 another type of matrices (adjacency matrices of certain bipartite graphs) are introduced. These matrices, called lossless expanders, can be used when reconstructing sparse vectors from a limited number of measurements. It is proved that, using adjacency matrices as measurement matrices, a stable and robust reconstruction of sparse vectors via \(\ell_1\)-minimization can be obtained. Finally, the stability and robustness of a thresholding-based algorithm and a simple sublinear-time algorithm are analyzed. Chapter 14 deals with recovery of random sparse signals with deterministic matrices. The results of this chapter are weaker than the ones of Chapter 5 in the sense that they apply only to most signals instead of all signals, but they show that the deterministic bounds using coherence may be somewhat pessimistic even if no bounds on the restricted isometry constants are available. Also, bounds on the conditioning of a random column submatrix of a given matrix are derived. The \(\ell_1\)-minimization plays a key role as a recovery method for compressive sensing. Algorithms designed specifically for \(\ell_1\)-minimization may be faster than general-purpose methods. In Chapter 15 several of these algorithms are introduced and analyzed. The picture of compressive sensing is the important feature of this book. The material presented here represents a solid foundation for the mathematical theory of compressive sensing.
- Minimal numerical differentiation formulas
- Signal recovery under cumulative coherence
- On the post selection inference constant under restricted isometry properties
- Sparse recovery from inaccurate saturated measurements
- Improved bounds for sparse recovery from subsampled random convolutions
- A primal-dual homotopy algorithm for \(\ell _{1}\)-minimization with \(\ell _{\infty }\)-constraints
- Global optimization for low-dimensional switching linear regression and bounded-error estimation
- On Dvoretzky's theorem for subspaces of \(L_p\)
- Infinite-dimensional compressed sensing and function interpolation
- Compressed sensing for real measurements of quaternion signals
- A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages
- On the uniqueness of the sparse signals reconstruction based on the missing samples variation analysis
- Expander \(\ell_0\)-decoding
- PROMP: a sparse recovery approach to lattice-valued signals
- Nonlinear approximation with nonstationary Gabor frames
- Compressed sensing and its applications. Second international MATHEON conference, December 2015
- An LP empirical quadrature procedure for parametrized functions
- Polynomials with bounds and numerical approximation
- Analysis of the equivalence relationship between \(l_{0}\)-minimization and \(l_{p}\)-minimization
- Random sampling of bandlimited signals on graphs
- Density theorems for nonuniform sampling of bandlimited functions using derivatives or bunched measurements
- A hierarchical framework for recovery in compressive sensing
- Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
- A Rice method proof of the null-space property over the Grassmannian
- Compressed sensing with structured sparsity and structured acquisition
- An analysis of the SPARSEVA estimate for the finite sample data case
- Accelerated first-order methods for hyperbolic programming
- Enhancing matrix completion using a modified second-order total variation
- Moving horizon estimation for ARMAX processes with additive output noise
- Signal recovery under mutual incoherence property and oracle inequalities
- Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
- Greedy subspace pursuit for joint sparse recovery
- Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
- Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
- Spark-level sparsity and the _1 tail minimization
- Column normalization of a random measurement matrix
- Inpainting via high-dimensional universal shearlet systems
- Approximately normalized iterative hard thresholding for nonlinear compressive sensing
- Compressive sensing in signal processing: algorithms and transform domain formulations
- Norm-minimized scattering data from intensity spectra
- Efficient dictionary learning with sparseness-enforcing projections
- Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
- The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Sparse approximate reconstruction decomposed by two optimization problems
- Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction
- Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing
- Single snapshot DOA estimation by minimizing the fraction function in sparse recovery
- Learning general sparse additive models from point queries in high dimensions
- An algebraic perspective on integer sparse recovery
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- Complexity and applications of the homotopy principle for uniformly constrained sparse minimization
- Stochastic greedy algorithms for multiple measurement vectors
- Sparse random matrices have simple spectrum
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- An introduction to compressed sensing
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Low-rank matrix recovery via regularized nuclear norm minimization
- Random sampling and reconstruction of concentrated signals in a reproducing kernel space
- Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
- Data-driven algorithm selection and tuning in optimization and signal processing
- A Laplacian approach to _1-norm minimization
- On the optimal constants in the two-sided Stechkin inequalities
- Donoho-Logan large sieve principles for modulation and polyanalytic Fock spaces
- Tensor theta norms and low rank recovery
- Gelfand numbers of embeddings of Schatten classes
- Sparse recovery using the discrete cosine transform
- Dual-density-based reweighted \(\ell_1\)-algorithms for a class of \(\ell_0\)-minimization problems
- Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
- Optimal fast Johnson-Lindenstrauss embeddings for large data sets
- Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids
- Dimensionality reduction for \(k\)-distance applied to persistent homology
- Image multiplicative denoising using adaptive Euler's elastica as the regularization
- A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
- Robust non-parametric regression via incoherent subspace projections
- A simple recovery framework for signals with time-varying sparse support
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Sparsest piecewise-linear regression of one-dimensional data
- Recovering sparse networks: basis adaptation and stability under extensions
- Robust sparse recovery via a novel convex model
- Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
- Sufficient conditions for the uniqueness of solution of the weighted norm minimization problem
- The uniform sparse FFT with application to PDEs with random coefficients
- Sensitivity of low-rank matrix recovery
- Generalization bounds for sparse random feature expansions
- The sparsity of LASSO-type minimizers
- Hierarchical compressed sensing
- Proof methods for robust low-rank matrix recovery
- New challenges in covariance estimation: multiple structures and coarse quantization
- Sparse deterministic and stochastic channels: identification of spreading functions and covariances
- Analysis of sparse recovery algorithms via the replica method
- Recovery under side constraints
- Compressive sensing and neural networks from a statistical learning perspective
- Compressed sensing in the spherical near-field to far-field transformation
- Single-pass randomized QLP decomposition for low-rank approximation
- A note on the invertibility of the Gabor frame operator on certain modulation spaces
- Weighted \(\ell_p\) (\(0<p\le 1\)) minimization with non-uniform weights for sparse recovery under partial support information
- Approximation spaces of deep neural networks
- Robust and resource-efficient identification of two hidden layer neural networks
- Hierarchical isometry properties of hierarchical measurements
This page was built for publication: A mathematical introduction to compressive sensing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q351503)
