Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPhase retrieval of complex-valued objects via a randomized Kaczmarz method
85
0
0.0
(
0
)
Added by
Teng Zhang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper investigates the convergence of the randomized Kaczmarz algorithm for the problem of phase retrieval of complex-valued objects. While this algorithm has been studied for the real-valued case}, its generalization to the complex-valued case is nontrivial and has been left as a conjecture. This paper establishes the connection between the convergence of the algorithm and the convexity of an objective function. Based on the connection, it demonstrates that when the sensing vectors are sampled uniformly from a unit sphere and the number of sensing vectors $m$ satisfies $m>O(nlog n)$ as $n, mrightarrowinfty$, then this algorithm with a good initialization achieves linear convergence to the solution with high probability.
rate research
Read More
In this paper, we analyze the convergence behavior of the randomized extended Kaczmarz (REK) method for all types of linear systems (consistent or inconsistent, overdetermined or underdetermined, full-rank or rank-deficient). The analysis shows that the larger the singular value of $A$ is, the faster the error decays in the corresponding right singular vector space, and as $krightarrowinfty$, $x_{k}-x_{star}$ tends to the right singular vector corresponding to the smallest singular value of $A$, where $x_{k}$ is the $k$th approximation of the REK method and $x_{star}$ is the minimum $ell_2 $-norm least squares solution. These results explain the phenomenon found in the extensive numerical experiments appearing in the literature that the REK method seems to converge faster in the beginning. A simple numerical example is provided to confirm the above findings.
This paper is concerned with stable phase retrieval for a family of phase retrieval models we name locally stable and conditionally connected (LSCC) measurement schemes. For every signal $f$, we associate a corresponding weighted graph $G_f$, defined by the LSCC measurement scheme, and show that the phase retrievability of the signal $f$ is determined by the connectivity of $G_f$. We then characterize the phase retrieval stability of the signal $f$ by two measures that are commonly used in graph theory to quantify graph connectivity: the Cheeger constant of $G_f$ for real valued signals, and the algebraic connectivity of $G_f$ for complex valued signals. We use our results to study the stability of two phase retrieval models that can be cast as LSCC measurement schemes, and focus on understanding for which signals the curse of dimensionality can be avoided. The first model we discuss is a finite-dimensional model for locally supported measurements such as the windowed Fourier transform. For signals without large holes, we show the stability constant exhibits only a mild polynomial growth in the dimension, in stark contrast with the exponential growth which uniform stability constants tend to suffer from; more precisely, in $R^d$ the constant grows proportionally to $d^{1/2}$, while in $C^d$ it grows proportionally to $d$. We also show the growth of the constant in the complex case cannot be reduced, suggesting that complex phase retrieval is substantially more difficult than real phase retrieval. The second model we consider is an infinite-dimensional phase retrieval problem in a principal shift invariant space. We show that despite the infinite dimensionality of this model, signals with monotone exponential decay will have a finite stability constant. In contrast, the stability bound provided by our results will be infinite if the signals decay is polynomial.
With a quite different way to determine the working rows, we propose a novel greedy Kaczmarz method for solving consistent linear systems. Convergence analysis of the new method is provided. Numerical experiments show that, for the same accuracy, our method outperforms the greedy randomized Kaczmarz method and the relaxed greedy randomized Kaczmarz method introduced recently by Bai and Wu [Z.Z. BAI AND W.T. WU, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), pp. A592--A606; Z.Z. BAI AND W.T. WU, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), pp. 21--26] in term of the computing time.
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).
The randomized sparse Kaczmarz method was recently proposed to recover sparse solutions of linear systems. In this work, we introduce a greedy variant of the randomized sparse Kaczmarz method by employing the sampling Kaczmarz-Motzkin method, and prove its linear convergence in expectation with respect to the Bregman distance in the noiseless and noisy cases. This greedy variant can be viewed as a unification of the sampling Kaczmarz-Motzkin method and the randomized sparse Kaczmarz method, and hence inherits the merits of these two methods. Numerically, we report a couple of experimental results to demonstrate its superiority
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
