Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices

Shuai Huang, Sidharth Gupta, Ivan Dokmanic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We tackle the problem of recovering a complex signal x n from quadratic measurements of the form y = xAix, where \left\{ {{{\mathbf{A}}-i}} \right\}-{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 Ai 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.

Original languageEnglish (US)
Title of host publication2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages5596-5600
Number of pages5
ISBN (Electronic)9781479981311
DOIs
StatePublished - May 2019
Event44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Brighton, United Kingdom
Duration: May 12 2019May 17 2019

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2019-May
ISSN (Print)1520-6149

Conference

Conference44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
CountryUnited Kingdom
CityBrighton
Period5/12/195/17/19

Fingerprint

Imaging techniques
Recovery
Geometry
Experiments

Keywords

  • Complex quadratic equations
  • low rank matrix recovery
  • phase retrieval
  • random Gaussian matrices
  • spectral initialization

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

Huang, S., Gupta, S., & Dokmanic, I. (2019). Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings (pp. 5596-5600). [8683280] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2019.8683280

Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices. / Huang, Shuai; Gupta, Sidharth; Dokmanic, Ivan.

2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 5596-5600 8683280 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, S, Gupta, S & Dokmanic, I 2019, Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices. in 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings., 8683280, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2019-May, Institute of Electrical and Electronics Engineers Inc., pp. 5596-5600, 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019, Brighton, United Kingdom, 5/12/19. https://doi.org/10.1109/ICASSP.2019.8683280
Huang S, Gupta S, Dokmanic I. Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 5596-5600. 8683280. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2019.8683280
Huang, Shuai ; Gupta, Sidharth ; Dokmanic, Ivan. / Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices. 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 5596-5600 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).
@inproceedings{3d3909eb6c5642ebb3fa7ce4b7af138d,
title = "Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices",
abstract = "We tackle the problem of recovering a complex signal x n from quadratic measurements of the form y = xAix, where \left\{ {{{\mathbf{A}}-i}} \right\}-{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 Ai 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.",
keywords = "Complex quadratic equations, low rank matrix recovery, phase retrieval, random Gaussian matrices, spectral initialization",
author = "Shuai Huang and Sidharth Gupta and Ivan Dokmanic",
year = "2019",
month = "5",
doi = "10.1109/ICASSP.2019.8683280",
language = "English (US)",
series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "5596--5600",
booktitle = "2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings",
address = "United States",

}

TY - GEN

T1 - Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices

AU - Huang, Shuai

AU - Gupta, Sidharth

AU - Dokmanic, Ivan

PY - 2019/5

Y1 - 2019/5

N2 - We tackle the problem of recovering a complex signal x n from quadratic measurements of the form y = xAix, where \left\{ {{{\mathbf{A}}-i}} \right\}-{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 Ai 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.

AB - We tackle the problem of recovering a complex signal x n from quadratic measurements of the form y = xAix, where \left\{ {{{\mathbf{A}}-i}} \right\}-{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 Ai 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.

KW - Complex quadratic equations

KW - low rank matrix recovery

KW - phase retrieval

KW - random Gaussian matrices

KW - spectral initialization

UR - http://www.scopus.com/inward/record.url?scp=85068980674&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068980674&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2019.8683280

DO - 10.1109/ICASSP.2019.8683280

M3 - Conference contribution

AN - SCOPUS:85068980674

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 5596

EP - 5600

BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -