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)