Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
70
0
0.0
(
0
)
Added by
Yue Lu
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present the optimal design of a spectral method widely used to initialize nonconvex optimization algorithms for solving phase retrieval and other signal recovery problems. Our work leverages recent results that provide an exact characterization of the performance of the spectral method in the high-dimensional limit. This characterization allows us to map the task of optimal design to a constrained optimization problem in a weighted $L^2$ function space. The latter has a closed-form solution. Interestingly, under a mild technical condition, our results show that there exists a fixed design that is uniformly optimal over all sampling ratios. Numerical simulations demonstrate the performance improvement brought by the proposed optimal design over existing constructions in the literature. In a recent work, Mondelli and Montanari have shown the existence of a weak reconstruction threshold below which the spectral method cannot provide useful estimates. Our results serve to complement that work by deriving the fundamental limit of the spectral method beyond the aforementioned threshold.
rate research
Read More
We demonstrate that a sparse signal can be estimated from the phase of complex random measurements, in a phase-only compressive sensing (PO-CS) scenario. With high probability and up to a global unknown amplitude, we can perfectly recover such a signal if the sensing matrix is a complex Gaussian random matrix and the number of measurements is large compared to the signal sparsity. Our approach consists in recasting the (non-linear) PO-CS scheme as a linear compressive sensing model. We built it from a signal normalization constraint and a phase-consistency constraint. Practically, we achieve stable and robust signal direction estimation from the basis pursuit denoising program. Numerically, robust signal direction estimation is reached at about twice the number of measurements needed for signal recovery in compressive sensing.
We consider the phase retrieval problem, in which the observer wishes to recover a $n$-dimensional real or complex signal $mathbf{X}^star$ from the (possibly noisy) observation of $|mathbf{Phi} mathbf{X}^star|$, in which $mathbf{Phi}$ is a matrix of size $m times n$. We consider a emph{high-dimensional} setting where $n,m to infty$ with $m/n = mathcal{O}(1)$, and a large class of (possibly correlated) random matrices $mathbf{Phi}$ and observation channels. Spectral methods are a powerful tool to obtain approximate observations of the signal $mathbf{X}^star$ which can be then used as initialization for a subsequent algorithm, at a low computational cost. In this paper, we extend and unify previous results and approaches on spectral methods for the phase retrieval problem. More precisely, we combine the linearization of message-passing algorithms and the analysis of the emph{Bethe Hessian}, a classical tool of statistical physics. Using this toolbox, we show how to derive optimal spectral methods for arbitrary channel noise and right-unitarily invariant matrix $mathbf{Phi}$, in an automated manner (i.e. with no optimization over any hyperparameter or preprocessing function).
In phase retrieval we want to recover an unknown signal $boldsymbol xinmathbb C^d$ from $n$ quadratic measurements of the form $y_i = |langle{boldsymbol a}_i,{boldsymbol x}rangle|^2+w_i$ where $boldsymbol a_iin mathbb C^d$ are known sensing vectors and $w_i$ is measurement noise. We ask the following weak recovery question: what is the minimum number of measurements $n$ needed to produce an estimator $hat{boldsymbol x}(boldsymbol y)$ that is positively correlated with the signal $boldsymbol x$? We consider the case of Gaussian vectors $boldsymbol a_i$. We prove that - in the high-dimensional limit - a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For $nle d-o(d)$ no estimator can do significantly better than random and achieve a strictly positive correlation. For $nge d+o(d)$ a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theory arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper and lower bound generalize beyond phase retrieval to measurements $y_i$ produced according to a generalized linear model. As a byproduct of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.
Compressive sensing has shown significant promise in biomedical fields. It reconstructs a signal from sub-Nyquist random linear measurements. Classical methods only exploit the sparsity in one domain. A lot of biomedical signals have additional structures, such as multi-sparsity in different domains, piecewise smoothness, low rank, etc. We propose a framework to exploit all the available structure information. A new convex programming problem is generated with multiple convex structure-inducing constraints and the linear measurement fitting constraint. With additional a priori information for solving the underdetermined system, the signal recovery performance can be improved. In numerical experiments, we compare the proposed method with classical methods. Both simulated data and real-life biomedical data are used. Results show that the newly proposed method achieves better reconstruction accuracy performance in term of both L1 and L2 errors.
In this paper, we propose a generalized expectation consistent signal recovery algorithm to estimate the signal $mathbf{x}$ from the nonlinear measurements of a linear transform output $mathbf{z}=mathbf{A}mathbf{x}$. This estimation problem has been encountered in many applications, such as communications with front-end impairments, compressed sensing, and phase retrieval. The proposed algorithm extends the prior art called generalized turbo signal recovery from a partial discrete Fourier transform matrix $mathbf{A}$ to a class of general matrices. Numerical results show the excellent agreement of the proposed algorithm with the theoretical Bayesian-optimal estimator derived using the replica method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
