Compressive Sensing ((Convex) Optimization Algorithms (Problem to solve…
(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)
Conditions on A for possible recovery sparse vector
Null space property: necessary & sufficient algebraic conditions, but difficult to verify
stable null space property: for stable recovery of compressible vector;
I robust null space property: for robust recovery (under small perturbation of measurement).
I Mutual Incoherence
simple sufficient condition, but not sharp
Small µ or µ_1
I Restrict Isometry Property (RIP)
A satisfies RIP of order s if δs is small.
sharp sufficient condition, but may be hard to verify.
What kinds of A for possible recovery of sparse vector
I Subgaussian Random matrices (Gaussian, Bernoulli, ...)
I Random sampling BOS (Fourier, wavelets, etc.)
Three Algorithms: min ||z||_0 subject to Az = y.
Solve a convex relaxation problem (1-norm problem)
Matching Pursuit (greedy algorithm)