Compressive Sensing
Three Algorithms: min ||z||_0 subject to Az = y.
Basis Pursuit
Matching Pursuit (greedy algorithm)
Thresholding-based methods
Conditions on A for possible recovery sparse vector
What kinds of A for possible recovery of sparse vector
I Random sampling BOS (Fourier, wavelets, etc.)
Solve a convex relaxation problem (1-norm problem)
I Subgaussian Random matrices (Gaussian, Bernoulli, ...)
Null space property: necessary & sufficient algebraic conditions, but difficult to verify
I Mutual Incoherence
I Restrict Isometry Property (RIP)
stable null space property: for stable recovery of compressible vector;
I robust null space property: for robust recovery (under small perturbation of measurement).
A satisfies RIP of order s if δs is small.
simple sufficient condition, but not sharp
sharp sufficient condition, but may be hard to verify.
Small µ or µ_1
(Convex) Optimization Algorithms
Problem to solve (Assume convexity)
min f(x) subject to y = Ax
min f1(x) + f2(Ax)
Basic convex analysis
I Gradient methods and Newton’s methods
I Proximal algorithms
I Augmented Lagrange Method (ALM) and Alternative Direction Method of Multipliers (ADMM)