compressive Sensing

Introduction

Faithfully and efficiently constructing signal from the coded signal is an age old scientific problem. Shannon/ Nyquist sampling theorem states that in-order to reconstruct signal from captured signal it should be sampled at least twice faster than the maximum signal bandwidth. However, for many practical applications like imaging system the Nyquist sampling rate is very high, paving path to look for alternative methods. To avoid high sampling rate signal compression is one such approach. In this paper summary a method of compressive sensing is outlined. Compressive sensing is a method to capture and represent compressible signals at a rate significantly below Nyquist rate. This method employs nonadaptive linear projections that maintains the structure of signals which is then reconstructed from the optimization technique as outline in <ref name="R1"> C. Dick, F. Harris, and M. Rice, “Synchronization in software defined radios—Carrier and timing recovery using FPGAs,” in Proc. IEEE Symp. Field-Programmable Custom Computing Machines, NapaValley, CA, pp. 195–204, Apr. 2000.</ref> <ref name="R2">J. Valls, T. Sansaloni, A. Perez-Pascual, V. Torres, and V. Almenar, “The use of CORDIC in software defined radios: A tutorial,” IEEE Commun. Mag., vol. 44, no. 9, pp. 46–50, Sept. 2006.</ref>.

In summary, in this paper we will learn the definition of compressible signal, constructing compressible signal and then reconstructing the compressed signal.

Compressible Signals

Let us, define a discrete time signal x such that it has following properties

• Real valued
• Finite length
• One dimensional

x has [math]\displaystyle{ N \times 1 }[/math] column vector in R ^N with elements x[n], n=1,2,....N. To define signal in [math]\displaystyle{ R\lt sup\gt N }[/math] we define [math]\displaystyle{ N \times 1 }[/math] vectors [math]\displaystyle{ \psi^{N}_{i} }[/math]. To keep it simple assume that basis is orthonormal. Using [math]\displaystyle{ N \times N }[/math] basis matrix [math]\displaystyle{ \psi = [\psi_1|\psi_2|......|\psi_N] }[/math] , Therefore signal x can be expressed as
[math]\displaystyle{ x=\sum_{i=1}^N s_{i} \psi_{i} }[/math] or [math]\displaystyle{ x=\psi s }[/math]
Where s is [math]\displaystyle{ N \times 1 }[/math] column vector of weighting coefficients
[math]\displaystyle{ s_i=\langle x,\psi_i \rangle=\psi^{T}_i x }[/math]
The signal is K-sparse if it is a linear combination of only K basis vector. The signal will be compressible if the above representation has just few large coefficient and many small coefficients. Please note that the above definition has following inefficiency

• The initial number of samples may be very large even if desired K is small.
• Set of all N transform coefficient [math]\displaystyle{ s_i }[/math] must be calculated eventhough all but K of them will be discarded.
• Localization of the large coefficients must be encoded, thus introducing overhead.

The problem statement for compressive sensing problem

Compressive sensing directly acquires the compressed signal without going through the intermediate stage of acquiring N samples. In order to achieve that a general linear measurement process is defined such that it computes [math]\displaystyle{ M \lt N }[/math] inner products between x and a collection of vectors [math]\displaystyle{ \{\phi \}_{j=1}^M }[/math] as in
[math]\displaystyle{ y_{j}=\langle x, \phi_j \rangle }[/math]
Ordering the new measurement vectors [math]\displaystyle{ y_j }[/math] in a [math]\displaystyle{ M\times 1 }[/math] vector y and the measurement vectors [math]\displaystyle{ \phi_{j}^{T} }[/math] as rows in an [math]\displaystyle{ M \times N }[/math] matrix [math]\displaystyle{ \phi }[/math]. then using previous definition we have
[math]\displaystyle{ y=\phi x=\phi \psi s=\theta s }[/math]
Where[math]\displaystyle{ \theta=\phi \psi }[/math] is an [math]\displaystyle{ M \times N }[/math] matrix. This measurement process in nonadaptive which implies that [math]\displaystyle{ \phi }[/math] is fixed and does not depend on the signal x. This now leads to following condition for designing

• Constructing a stable measurement matrix [math]\displaystyle{ \phi }[/math] by preserving the information while reducing the dimension from N to M.
• Designing a reconstructing algorithm such that it recovers x from y by using only [math]\displaystyle{ M \approx K }[/math] measurements.

Constructing a Stable Measurement Matrix

The measurements matrix [math]\displaystyle{ \phi }[/math] must allow the reconstruction of the signal x from [math]\displaystyle{ M \lt N }[/math]. If, x is K-sparse and the locations of the nonzero coefficients in s are known, then problem can be solved provided [math]\displaystyle{ M \geq K }[/math]. To keep this problem well conditioned we have necessary and sufficient condition as
[math]\displaystyle{ 1-\epsilon \leq \frac{\parallel \theta v\parallel_2}{\parallel v\parallel_2}\leq 1+\epsilon }[/math]
Where v is a vector sharing the same non zero entries as s and [math]\displaystyle{ \epsilon \geq 0 }[/math]. This means [math]\displaystyle{ \theta }[/math] must preserve the lengths of these particular K-sparse vectors. This condition is referred to as restricted isometry property(RIP)<ref name="R1"> C. Dick, F. Harris, and M. Rice, “Synchronization in software defined radios—Carrier and timing recovery using FPGAs,” in Proc. IEEE Symp. Field-Programmable Custom Computing Machines, NapaValley, CA, pp. 195–204, Apr. 2000.</ref> <ref name="R2">J. Valls, T. Sansaloni, A. Perez-Pascual, V. Torres, and V. Almenar, “The use of CORDIC in software defined radios: A tutorial,” IEEE Commun. Mag., vol. 44, no. 9, pp. 46–50, Sept. 2006.</ref>. A similar property called incoherence is requires that the rows [math]\displaystyle{ \{\phi_j\} }[/math] of [math]\displaystyle{ \phi }[/math] cannot sparsely represent the columns [math]\displaystyle{ \{\psi_i\} }[/math] of [math]\displaystyle{ \psi }[/math]
The RIP and incoherence can be satisfied by choosing random matrix [math]\displaystyle{ \phi }[/math] most of the times. For example, let us construct a matrix [math]\displaystyle{ \phi_{j,i} }[/math] such that its matrix elements are independent and identically distributed (iid) random variables from a Gaussian probability distribution with mean zero and variance 1/N [1],[2],[4]. Therefore the measurements y are merely M different randomly weighted linear combinations of the elements of x. The matrix [math]\displaystyle{ \phi }[/math] has following properties,

1. The incoherence property is satisfied by matrix [math]\displaystyle{ \phi }[/math].
2. The [math]\displaystyle{ \phi }[/math] is universal that is it will satisfy the RIP property with high probability.

Reconstruction Algorithm

Now we are left with the task to design reconstruction algorithm.The reconstruction algorithm must take into account the M measurements in the vector y, the random measurement matrix [math]\displaystyle{ \phi }[/math] and the basis [math]\displaystyle{ \psi }[/math]. Then reconstruct the length N signal x or its sparse coefficient vector s. Since M<N then we have s^' which satisfies,
[math]\displaystyle{ \theta s_{'}=y }[/math]
The justification for this is that [math]\displaystyle{ \theta s=y }[/math] then [math]\displaystyle{ \theta (s+r)=y }[/math] for any vector r in the null space [math]\displaystyle{ N(\theta) }[/math] of [math]\displaystyle{ \theta }[/math]. This leads to finding signal's sparse coefficient vector in the (N-M) dimensional translated null space [math]\displaystyle{ H=N(\theta)+s }[/math], in-order to construct the signal. The reconstruction process can be attempted in the following ways,

• Minimum [math]\displaystyle{ l_2 }[/math] norm reconstruction

Recall that [math]\displaystyle{ \parallel l\parallel_p=sum_{i=1}^{N} |s_i|^p }[/math]. In-order to solve this type of problems the classical approach is to find the vector in the transformed null space with the smallest [math]\displaystyle{ l_2 }[/math] norm also called energy norm by solving.
[math]\displaystyle{ \hat{s}=argmin\parallel s_{'}\parallel_2 }[/math] such that [math]\displaystyle{ \theta s_{'}=y }[/math]
The closed form solution is given by [math]\displaystyle{ \hat{s}=\theta_{T}(\theta \theta_{t})^{-1}y }[/math]. However the minimization returns non-sparse [math]\displaystyle{ \hat{s} }[/math] with many non zero elements in other words it almost never able to reconstruct the actual signal.

• Minimum [math]\displaystyle{ l_0 }[/math] norm reconstruction

Let us now evaluate the [math]\displaystyle{ l_0 }[/math] norm which counts the number of non-zero entries in s.
[math]\displaystyle{ \hat{s}=argmin\parallel s_{'}\parallel_0 }[/math] such that [math]\displaystyle{ \theta s_{'}=y }[/math]
At first glance it looks attractive as it recovers the K-sparse signal exactly with high probability using only M=K+1 iid Gaussian measurements. However, solving the equation is numerically unstable and NP-complete which requires exhaustive search of all [math]\displaystyle{ (_K^{N}) }[/math] possible localization of the non-zero entries in s.

• Minimum [math]\displaystyle{ l_1 }[/math] norm reconstruction

Now, if perform minimization on [math]\displaystyle{ l_1 }[/math] norm
is able to recover K-sparse signals and closely approximate compressible signal with high probability using only [math]\displaystyle{ M \geq cKlog(\frac{N}{K}) }[/math] iid Gaussian measurements.
[math]\displaystyle{ \hat{s}=argmin\parallel s_{'}\parallel_1 }[/math] such that [math]\displaystyle{ \theta s_{'}=y }[/math]
This optimization is convex optimization problem which reduces to linear program basis pursuit<ref name="R1"> C. Dick, F. Harris, and M. Rice, “Synchronization in software defined radios—Carrier and timing recovery using FPGAs,” in Proc. IEEE Symp. Field-Programmable Custom Computing Machines, NapaValley, CA, pp. 195–204, Apr. 2000.</ref> <ref name="R2">J. Valls, T. Sansaloni, A. Perez-Pascual, V. Torres, and V. Almenar, “The use of CORDIC in software defined radios: A tutorial,” IEEE Commun. Mag., vol. 44, no. 9, pp. 46–50, Sept. 2006.</ref>, having computational complexity[math]\displaystyle{ O(n^3) }[/math].

Conclusion

The compressive sensing can be applied to analog signals as well. The sensing technique finds many practical application in image processing and similar fields. In this summary we learned the method of compressive sensing which more efficient compared to traditional techniques.

References

<references />