Bhairav Bipin Mehta^{1}, Mingrui Yang^{2}, and Mark Alan Griswold^{1}

Compressed sensing (CS) has been extensively used with wide spread application in MRI and other signal processing fields. Spark of the sensing matrix is at the heart of the CS framework for determining the success of the signal recovery for a given designed CS system. However, estimation of Spark of the sensing matrix is a combinatorial process, thus, practically difficult to estimate for realistic sizes of sensing matrices. The purpose of this work is to present a new optimization-problem-based approach for estimation of the Spark of the sensing matrix which will overcome the existing limitations, thereby, a tool to assess and design CS framework based systems.

In general, we are looking to solve the following inverse problem

$$Sx_0=y\quad\quad\quad(1)$$

where $$$S\in\mathbb{C}^{M\times N}$$$ is the sensing matrix with $$$M<N,x_0\in\mathbb{C}^{N}$$$ is the ground truth object in the desired transform domain and $$$y\in\mathbb{C}^{M}$$$ is the sampled data. The solution space for a given $$$S$$$ and $$$y$$$ is

$$\{x |x=x_0+n,n\in null(S)\}\quad\quad\quad(2)$$

Donoho
*et. al.*^{[3]} defined Spark
of matrix A, as the smallest possible number of columns from A that are
linearly dependent. Using this definition Donoho *et. al.*^{[3]} laid down the theoretical limit and thereby
the sampling theorem of the CS framework. They proved that, for any $$$k$$$-sparse, $$$x_0$$$, to
be the sparsest element within the solution space, the following condition
should be satisfied^{[3]}

$$\parallel\space n\space\parallel_0\space>\space2k\quad\quad\forall\space n\in\{n|Sn=\bar{0},n\neq\bar{0}\}\quad\quad\quad(3)$$

Thus,
Spark is at the heart of the assessment of guaranteed signal recovery for a
given system. The brute force approach to estimate Spark requires combinatorial
assessment of the columns of the sensing matrix. To the best of our knowledge,
currently there is no approach for estimating Spark in practically feasible
time for realistic sizes of sensing matrices. Mutual coherence is a surrogate
measure and could be far away from the actual value of the Spark^{[2,3,5]}. Since Spark
is by definition the $$$\ell_0$$$ norm of the sparsest element of the subspace $$$\{ n|Sn=\bar{0},n\neq \bar{0}\}$$$, we
propose to estimate Spark by solving the following optimization problem.

$$\min_n\space\parallel n\parallel_1\quad\quad subject\space to\space Sn=\bar{0} \space and\space\parallel n\parallel_2=1\quad\quad\quad(4)$$

where Spark would be the $$$\ell_0$$$ norm of the solution of the optimization problem in equation (4).

1. D. L. Donoho, “Compressed sensing,” IEEE Trans. Info. Theory, vol. 52, no. 4, pp. 1289–1306, Sep. 2006.

2. E. J. Candes, “Compressive sampling,” in Int. Congress of Mathematicians, Madrid, Spain, 2006, vol. 3, pp. 1433–1452.

3. D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via $$$\ell_1$$$ minimization,” Proc.Nat. Acad. Sci., vol. 100, no. 5, pp. 2197–2202, Mar. 2003.

4. M. Lustig, D. L. Donoho, and J. M. Pauly, “Sparse MRI: The application of compressed sensing for rapid MR imaging,” Magn. Res. Med.,vol. 58, no. 6, pp. 1182-1195, Dec. 2008.

5. M. Duarte and Y. Eldar, “Structured compressed sensing: From theoryto applications,” IEEE Trans. Signal Process., vol. 59, no. 9, pp. 4053–4085, Sep. 2011.

6. E. J. Candes, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Comm. Pure Appl.Math., vol. 59, no. 8, pp. 1207–1223, 2006.