Please enable JavaScript.
Coggle requires JavaScript to display documents.
Compressive Sensing ((Convex) Optimization Algorithms (Problem to solve…
Compressive Sensing
(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
What kinds of A for possible recovery of sparse vector
I Random sampling BOS (Fourier, wavelets, etc.)
I Subgaussian Random matrices (Gaussian, Bernoulli, ...)
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.
Three Algorithms: min ||z||_0 subject to Az = y.
Basis Pursuit
Solve a convex relaxation problem (1-norm problem)
Matching Pursuit (greedy algorithm)
Thresholding-based methods