skip to main content


Title: 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
NSF-PAR ID:
10120565
Author(s) / Creator(s):
; ;
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
  1. 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
  2. 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
  3. 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
  4. In two-phase materials, each phase having a non-local response in time, it has been found that for some driving fields the response somehow untangles at specific times, and allows one to directly infer useful information about the geometry of the material, such as the volume fractions of the phases. Motivated by this, and to obtain an algorithm for designing appropriate driving fields, we find approximate, measure independent, linear relations between the values that Markov functions take at a given set of possibly complex points, not belonging to the interval [-1,1] where the measure is supported. The problem is reduced to simply one of polynomial approximation of a given function on the interval [-1,1] and, to simplify the analysis, Chebyshev approximation is used. This allows one to obtain explicit estimates of the error of the approximation, in terms of the number of points and the minimum distance of the points to the interval [-1,1]. Assuming this minimum distance is bounded below by a number greater than 1/2, the error converges exponentially to zero as the number of points is increased. Approximate linear relations are also obtained that incorporate a set of moments of the measure. In the context of the motivating problem, the analysis also yields bounds on the response at any particular time for any driving field, and allows one to estimate the response at a given frequency using an appropriately designed driving field that effectively is turned on only for a fixed interval of time. The approximation extends directly to Markov-type functions with a positive semidefinite operator valued measure, and this has applications to determining the shape of an inclusion in a body from boundary flux measurements at a specific time, when the time-dependent boundary potentials are suitably tailored. 
    more » « less
  5. 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