An official website of the United States government
Abstract We study the low-rank phase retrieval problem, where our goal is to recover a $$d_1\times d_2$$ low-rank matrix from a series of phaseless linear measurements. This is a fourth-order inverse problem, as we are trying to recover factors of a matrix that have been observed, indirectly, through some quadratic measurements. We propose a solution to this problem using the recently introduced technique of anchored regression. This approach uses two different types of convex relaxations: we replace the quadratic equality constraints for the phaseless measurements by a search over a polytope and enforce the rank constraint through nuclear norm regularization. The result is a convex program in the space of $$d_1 \times d_2$$ matrices. We analyze two specific scenarios. In the first, the target matrix is rank-$$1$$, and the observations are structured to correspond to a phaseless blind deconvolution. In the second, the target matrix has general rank, and we observe the magnitudes of the inner products against a series of independent Gaussian random matrices. In each of these problems, we show that anchored regression returns an accurate estimate from a near-optimal number of measurements given that we have access to an anchor matrix of sufficient quality. We also show how to create such an anchor in the phaseless blind deconvolution problem from an optimal number of measurements and present a partial result in this direction for the general rank problem.
more »
« less
Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices
We tackle the problem of recovering a complex signal $$\vx\in\mathbb{C}^n$$ from quadratic measurements of the form $$y_i=\vx^*\vA_i\vx$$, where $$\{\vA_i\}_{i=1}^m$$ is a set of complex iid standard Gaussian matrices. This non-convex problem is related to the well understood phase retrieval problem where $$\vA_i$$ is a rank-1 positive semidefinite matrix. Here we study a general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior work either addresses the rank-1 case or focuses on real measurements. The several papers that address the full-rank complex case adopt the semidefinite relaxation approach and are thus computationally demanding. In this paper we propose a method based on the standard framework comprising a spectral initialization followed by iterative gradient descent updates. We prove that when the number of measurements exceeds the signal's length by some constant factor, a globally optimal solution can be recovered from complex quadratic measurements with high probability. Numerical experiments on simulated data corroborate our theoretical analysis.
more »
« less
- Award ID(s):
- 1817577
- PAR ID:
- 10120565
- Date Published:
- Journal Name:
- ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- Page Range / eLocation ID:
- 5596 to 5600
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of estimating the output of an unknown discrete-time linear time-invariant system and identifying a model of the system, where only measurements via a nonlinear dynamic sensor with known dynamics are available. The main result of this paper is a rank-constrained semidefinite program, which provides an equivalent characterization of this identification and estimation problem. This extends existing results from Wiener system identification to the more general case that the nonlinear block exhibits dynamic behavior, which is a commonly found scenario in practical applications. Notably, the result can be applied in the presence of nonlinear sensors with general non-invertible system dynamics. Two examples are used to illustrate the applicability of our approach.more » « less
-
In this paper, we present CPL-Sync, a certifiably correct algorithm to solve planar pose graph optimization (PGO) using the complex number representation. We formulate planar PGO as the maximum likelihood estimation (MLE) on the product of unit complex numbers, and relax this nonconvex quadratic complex optimization problem to complex semidefinite programming (SDP). Furthermore, we simplify the corresponding semidefinite programming to Riemannian staircase optimization (RSO) on complex oblique manifolds that can be solved with the Riemannian trust region (RTR) method. In addition, we prove that the SDP relaxation and RSO simplification are tight as long as the noise magnitude is below a certain threshold. The efficacy of this work is validated through comparisons with existing methods as well as applications on planar PGO in simultaneous localization and mapping (SLAM), which indicates that the proposed algorithm is more efficient and capable of solving planar PGO certifiably. The C++ code for CPL-Sync is available at https://github. com/fantaosha/CPL- Sync.more » « less
-
Blind sensor calibration for spectrum estimation is the problem of estimating the unknown sensor calibration parameters as well as the parameters-of-interest of the impinging signals simultaneously from snapshots of measurements obtained from an array of sensors. In this paper, we consider blind phase and gain calibration (BPGC) problem for direction-of-arrival estimation with multiple snapshots of measurements obtained from an uniform array of sensors, where each sensor is perturbed by an unknown gain and phase parameter. Due to the unknown sensor and signal parameters, BPGC problem is a highly nonlinear problem. Assuming that the sources are uncorrelated, the covariance matrix of the measurements in a perfectly calibrated array is a Toeplitz matrix. Leveraging this fact, we first change the nonlinear problem to a linear problem considering certain rank-one positive semidefinite matrix, and then suggest a non-convex optimization approach to find the factor of the rank-one matrix under a unit norm constraint to avoid trivial solutions. Numerical experiments demonstrate that our proposed non-convex optimization approach provides better or competitive recovery performance than existing methods in the literature, without requiring any tuning parameters.more » « less
-
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICASSP.2019.8683280
