On Phase Transition of Compressed Sensing in the Complex Domain

I Introduction

Compressed sensing (CS) aims at recovering a signal from reduced number of linear measurements under a sparsity/compressibility condition. Different from the conventional linear recovery approach, a nonlinear scheme is used in CS to solve the following basis pursuit (BP) problem

The theory of CS is mainly focused on studying how aggressively a sparse signal can be undersampled while still preserving all information for its recovery. The existing results include those based on incoherence, restricted isometry property (RIP) and phase transition theory. While the incoherence and RIP are sufficient conditions for the sparse signal recovery and typically quite conservative in practice, the phase transition defined for $N\rightarrow\infty$ is most precise owing to its necessary and sufficient condition for measuring the sparsity-undersampling tradeoff performance. For the real valued CS (RVCS) using the sensing matrix A with i.i.d. random Gaussian entries, the sparsity-undersampling tradeoff of the BP is controlled by the sampling ratio $\delta=n/N$ and sparsity ratio $\rho=k/n$, where $k$ denotes the number of nonzero entries of x. As a result, the plane of $\left(\delta,\rho\right)$ is divided by a phase transition curve into two phases, a ‘success’ phase where BP successfully recovers the sparse signal and a ‘failure’ phase where the original signal cannot be recovered by solving BP, both with an overwhelming probability.

In RVCS, three different approaches, combinatorial geometry , null space method and state evolution , to the phase transition of BP have provided identical results. Numerical simulations have shown that the observed phase transition matches the theoretical curve even for modestly large $N$, e.g., $N=1000$ , where the phase transition for finite-$N$ is defined as the value of $\rho$ at which the original signal is successfully recovered with the probability of $50\%$. Moreover, it is practically observed that the Gaussian condition on A can be considerably relaxed, resulting in the well known observed universality of phase transitions .

To the best of our knowledge, the existing results on phase transition, before our preliminary work , only deal with the RVCS problem. This letter presents our first study of the phase transition in the more general complex domain where both the signal and sensing matrix are complex valued. Its significance is twofold: 1) discovering a new phase transition for the complex valued CS (CVCS) so to inspire completeness of the phase transition theory; 2) providing insight into performance of numerous CS applications involving complex data, e.g., magnetic resonance imaging (MRI), radar imaging and source localization.

The sparsity of a complex signal implies joint sparsity of its real and imaginary parts with the same support. This connects to the block-sparse CS (BSCS) problem which is to recover real valued signals with entries clustered into sparse blocks of equal size. The phase transition of the BSCS is analyzed in by Stojnic under the condition that the null space of the real valued random sensing matrix is distributed uniformly in the Grassmanian. It is shown in this letter that the phase transition of the CVCS coincides with that of the BSCS with the block size $2$. Analysis is further carried out to show that the phase transition of the CVCS is not a special case of that of the BSCS because the CVCS does not meet the aforementioned uniformly distributed null space condition.

Section II retrospects the main points in on ONE-L1 algorithms and extends the algorithms to the CVCS. Section III applies the extended ONE-L1 algorithms to explore the phase transition of CVCS and its connection to the BSCS. Conclusion is drawn in Section IV.

II ONE-L1 Algorithms for CVCS

The ONE-L1 algorithms solve the BP in RVCS where x, A and b are all real valued. Assume that the sensing matrix A is partially orthonormal, i.e., $\emph{{A}}\emph{{A}}^{\prime}=\emph{{I}}$ with ′ denoting the transpose and I being an identity matrix, and let $\Gamma({\emph{{d}}})$ be an operator projecting the vector d onto its first $n$ entries. The orthonormal expansion technique is to introduce an expanded orthonormal matrix $\Phi$ to reformulate the BP into

where the first $n$ rows of $\Phi$ compose A and the rest orthonormal $N-n$ rows are arbitrary.

The augmented Lagrange multiplier (ALM) method is applied in to $\left(\text{BP}^{o}\right)$ and the obtained result leads to an exact ONE-L1 (eONE-L1) algorithm for iterative computation of the optimal solution. While eONE-L1 has an inner iteration loop embedded in the outer loop iteration, its relaxed version, rONE-L1, further speeds up the computation by simplifying the inner loop iteration into a single update. The rONE-L1 algorithm is numerically optimal in terms of the sparsity-undersampling tradeoff under reasonable parameter settings, i.e., its phase transition result matches that of BP. It has been shown that rONE-L1 is of iterative thresholding type and is very fast, with appropriate settings of the regulation variable, in comparison with other state-of-the-art algorithms.

An important operation in the ONE-L1 algorithms is the soft thresholding defined as

for real valued vectors $\emph{{w}},\emph{{v}}$ of the same dimension.

III Phase Transition of CVCS

Section II has shown that the ONE-L1 algorithms can be extended and applicable to the CVCS problem. The eONE-L1 achieves the optimal solution of BP and rONE-L1 is numerically optimal and exponentially converges, which are applied in this subsection to empirically explore the sparsity-undersampling tradeoff of BP. The implementations of ONE-L1 algorithms follow the same procedure as their real versions in . We fix $r>1$ and let $\mu_{t+1}=r\cdot\mu_{t}$. The regulation parameter $r$ is set to $r=1+\delta$ in eONE-L1 and $r=\min\left(1+0.04\delta,1.02\right)$ is chosen in rONE-L1. The success of recovering the original signal is stated if the relative root mean squared error (RRMSE) $\left\|\hat{\emph{{x}}}-\emph{{x}}^{o}\right\|_{2}/\left\|\emph{{x}}^{o}\right\|_{2}<10^{-4}$, where $\emph{{x}}^{o}$ and $\hat{\emph{{x}}}$ are the original and recovered signals, respectively. Meanwhile, the failure in solving BP using ONE-L1 is stated if $\left\|\hat{\emph{{x}}}\right\|_{1}\geq\left(1+10^{-5}\right)\left\|\emph{{x}}^{o}\right\|_{1}$ and $\left\|\hat{\emph{{x}}}-\emph{{x}}^{o}\right\|_{2}/\left\|\emph{{x}}^{o}\right\|_{2}\geq 10^{-4}$.

Inspired by the estimation of the real phase transition in , we first set a complex matrix ensemble, e.g., Gaussian, and dimension $N$. A grid of $\left(\delta,\rho\right)$ is generated in the plane $\left[0,1\right]\times\left[0,1\right]$ with equispaced $\delta\in\left\{0.02,0.05,\cdots,0.98\right\}$ and $\rho\in\left\{\rho^{R}\left(\delta\right)+0.01(i-21):i=1,2,\cdots,41\right\}$ with respect to $\delta$, where $\rho^{R}\left(\delta\right)$ denotes the theoretical real phase transition as shown in Fig. 1. For each combination of $\left(\delta,\rho\right)$, $M=20$ random problem instances are generated and solved with $n=\lceil\delta N\rceil$ and $k=\lceil\rho n\rceil$. The number of success among $M$ instances is recorded. After data acquisition, a generalized linear modal (GLM) with a logistic link is used to estimate the phase transition.

We now explore the sparsity-undersampling tradeoff of BP with partial-Fourier sampling. Four values of signal length $N$ are considered, including 1024, 2048, 4096 and 8192. When $N=1024$, both eONE-L1 and rONE-L1 are used to estimate the phase transition of BP. The rONE-L1 algorithm is used for other $N$. Few failures in solving the BP occur when using rONE-L1. Fig. 1 presents the estimated phase transitions of partial-Fourier sampling. The five observed phase transitions of BP, estimated respectively by eONE-L1 with $N=1024$ and rONE-L1 with $N=1024$, 2048, 4096 and 8192, coincide with each other and are higher than the real phase transition of BP. Our earlier observation of the successful signal recovery rate reported in also showed that a larger $N$ results in sharper phase transition. Hence, we can state:

For complex signals and the partial-Fourier matrix ensemble with large dimension $N$, we observe that

BP exhibits phase transition in the plane of $\left(\delta,\rho\right)$, and a larger $N$ can result in a sharper phase transition.

the complex phase transition of BP is higher than the real phase transition with a considerably enlarged success phase.

III-B Universality of Phase Transitions of CVCS

The observed universality of phase transitions of BP in the real case has been discussed in and the same result is stated in . In this subsection, we examine whether the same property holds in the complex case. Apart from the partial-Fourier matrix ensemble, three other complex matrix ensembles are considered with signal length $N=1000$, including Gaussian, Bernoulli and Ternary. All random matrices have i.i.d. real and imaginary parts following the corresponding distributions. Bernoulli refers to equally likely being or $1$, and Ternary is equally likely to be $-1$, or $1$. It is noted that a matrix generated from these matrix ensembles may not be partially orthonormal as required by the ONE-L1 algorithms. This problem can always be resolved by left multiplying both sides of $\emph{{A}}\emph{{x}}=\emph{{b}}$ with an invertible matrix, e.g. using QR decomposition, so the transformed equation meets the partially orthonormal condition and preserves the same solution space.

Few failures in solving BP occur in our experiment. Fig. 2 presents the observed phase transitions of BP with different matrix ensembles. Like the universality of phase transitions in the real case, we have the following finding.

For complex signals and a number of complex matrix ensembles with large dimension $N$, BP exhibits the same phase transition.

III-C Connection of CVCS and BSCS

A comparison of the phase transition of CVCS with theoretical phase transition of BSCS with block size $2$ in is presented in Fig. 3. It is shown that the observed phase transition of CVCS coincides with that of BSCS.

In , the theoretical phase transition of BSCS is derived under the condition that the null space of the real valued random sensing matrix is distributed uniformly in the Grassmanian with respect to the Haar measure. It is known that the real Gaussian matrix ensemble satisfies such a condition . We now provide an analysis in the following proposition to show that such a condition is not satisfied in the CVCS problem. It therefore clarifies that the phase transition of the CVCS studied in this letter is not a special case of the phase transition result of BSCS in .

For any complex random matrix A associated with the CVCS problem, the null space of $\emph{{A}}_{r}$ is not distributed uniformly in the Grassmanian with respect to the Haar measure.

Proposition 1 shows that the existing phase transition theory of BSCS cannot explain our obtained empirical phase transition of the CVCS. Intuitively, the coincidence of the phase transition of CVCS with that of BSCS may be interpreted as the universality of phase transitions of BSCS across different matrix ensembles. Fig. 3 also shows that the observed phase transition by minimizing $\left\|\emph{{x}}_{r}\right\|_{1}$, subject to $\emph{{A}}\emph{{x}}=\emph{{b}}$ and without taking into account the block-sparsity, matches the real phase transition of BP. It further explains that the higher successful rate of CVCS is obtained by incorporating the block-sparsity factor into its problem solving.

IV Conclusion

In this letter, the sparsity-undersampling tradeoff of BP for the CVCS problem is empirically explored in terms of the phase transition. It is found that the same properties exist as those in the RVCS case, such as the existence of the phase transition and observed universality across different matrix ensembles. The empirical phase transition of CVCS presents larger successful phase than that of RVCS, indicating that more successful recoveries of complex signals can be achieved by incorporating the signal structure into the problem solving process. It is shown that the empirical phase transition of CVCS is connected to and coincides with that of BSCS with block size $2$. It is however not a special case of the existing phase transition theory of BSCS and can be intuitively interpreted as an extension of current results based on the universality argument. So far, the rigorous relationship between the phase transitions of CVCS and BSCS problems is still an open problem. It is finally noted that an analysis, based on a different algorithm, of the existence of the phase transition of CVCS and its expression that agrees with the results in this letter has been reported in during the preparation of this letter.

References