Inferring Basis Mismatch in image representations

Objective is to reduce problem of Basis mismatch using Alternating Convex Search.

Research Problem

In theory of compressive sensing,

where And

Here we have to determine original signal/image from Sensing matrix and measured signal/image . For becomes under-determined and does not have a closed form solution for (infinite many 's maps to same ).

But compressive sensing theory says we can uniquely estimate from and , given should be sparse in some basis matrix say (commonly DFT, DCT or wavelet) which is theoretically known and should be incoherent with .

So equation becomes,

where and .

In practice, even small deviation from exact signal can cause drastic increase in estimation error. This is called Basis Mismatch problem.

Note- Basis mismatch always exists because of noise or discrete representation of bases as the sensed signal is almost never going to lay on the exact grid of . So sparse signals w.r.t. sparsifying matrix could become non-sparse or less sparse under another matrix say , such that .

Therefore it remained the predominant question of how to reduce the Basis Mismatch effect?

Solution Approaches

Previous Approaches:

• Oversample the frequency space i.e. contain sinusoids with frequencies / apart instead of / apart.
• Treat both the model coefficients and the associated frequency as unknown which need to be solved. Isolates the unknown frequencies in separate, non-overlapping bins and then solves for their location and amplitude.
• Both frequency locations and amplitudes can be estimated by solving the constrained Atomic Norm Minimization by semi-definite programming. Also Atomic Norm Minimization constrain can be solved by greedy forward-backward (GFB) algorithm.

Proposed Approaches- Alternating Convex Search (ACS): This method is implemented as shown in this paper. Here, we solve the basis mismatch problem using Alternating Convex Search (ACS) which is trying to estimate both frequency bases matrix and coefficients.

This method uses standard to find out the signal model coefficients i.e. by keeping frequency parameter fixed. Then using this coefficients find out the signal model using component-wise minimization like coordinate descent on the frequency parameter. These steps are repeated this until convergence criteria is met.

Dependencies

MATLAB

References

• Compressed sensing by D. L. Donoho
• Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search by Jonathan M. Nichols, Albert K. Oh, and Rebecca M. Willett