TY - GEN
T1 - Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure
AU - Jagatap, Gauri
AU - Hegde, Chinmay
N1 - Funding Information:
This work was supported in part by NSF grants CCF-1566281 and CCF-1750920, and a Black and Veatch Faculty Fellowship.
Funding Information:
1This work was supported in part by NSF grants CCF-1566281 and CCF-1750920, and a Black and Veatch Faculty Fellowship.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/15
Y1 - 2018/8/15
N2 - We consider the problem of estimating a structured high-dimensional parameter vector using random Gaussian quadratic samples. This problem is a generalization of the classical problem of phase retrieval and impacts numerous problems in computational imaging. We provide a generic algorithm based on alternating minimization that, if properly initialized, achieves information-theoretically optimal sample complexity. In essence, we show that solving a system of random quadratic equations with structural constraints is (nearly) as easy as solving the corresponding linear system with the same constraints, if a proper initial guess of the solution is available. As an immediate consequence, our approach improves upon the best known existing sample complexity results for phase retrieval (structured or otherwise). We support our theory via several numerical experiments. A full version of this paper is accessible at: https://gaurijagatap.github.io/assets/ISIT18.pdf.
AB - We consider the problem of estimating a structured high-dimensional parameter vector using random Gaussian quadratic samples. This problem is a generalization of the classical problem of phase retrieval and impacts numerous problems in computational imaging. We provide a generic algorithm based on alternating minimization that, if properly initialized, achieves information-theoretically optimal sample complexity. In essence, we show that solving a system of random quadratic equations with structural constraints is (nearly) as easy as solving the corresponding linear system with the same constraints, if a proper initial guess of the solution is available. As an immediate consequence, our approach improves upon the best known existing sample complexity results for phase retrieval (structured or otherwise). We support our theory via several numerical experiments. A full version of this paper is accessible at: https://gaurijagatap.github.io/assets/ISIT18.pdf.
UR - http://www.scopus.com/inward/record.url?scp=85052448116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052448116&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2018.8437770
DO - 10.1109/ISIT.2018.8437770
M3 - Conference contribution
AN - SCOPUS:85052448116
SN - 9781538647806
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2296
EP - 2300
BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -