Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure

Gauri Jagatap, Chinmay Hegde

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

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages2296-2300
    Number of pages5
    ISBN (Print)9781538647806
    DOIs
    StatePublished - Aug 15 2018
    Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
    Duration: Jun 17 2018Jun 22 2018

    Publication series

    NameIEEE International Symposium on Information Theory - Proceedings
    Volume2018-June
    ISSN (Print)2157-8095

    Other

    Other2018 IEEE International Symposium on Information Theory, ISIT 2018
    CountryUnited States
    CityVail
    Period6/17/186/22/18

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Information Systems
    • Modeling and Simulation
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure'. Together they form a unique fingerprint.

  • Cite this

    Jagatap, G., & Hegde, C. (2018). Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure. In 2018 IEEE International Symposium on Information Theory, ISIT 2018 (pp. 2296-2300). [8437770] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2018.8437770