Fast Low-Rank Matrix Estimation for Ill-Conditioned Matrices

Mohammadreza Soltani, Chinmay Hegde

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

    Abstract

    We study the general problem of optimizing a convex function of a matrix-valued variable subject to low-rank constraints. This problem has attracted significant attention; however, existing first-order methods for solving such problems either are too slow to converge, or require multiple invocations of singular value decompositions. On the other hand, factorization-based non-convex algorithms, while being much faster, require stringent assumptions on the condition number of the optimum. In this paper, we provide a novel algorithmic framework that achieves the best of both worlds: as fast as factorization methods, while requiring no spectral assumptions. We instantiate our framework for the nonlinear affine rank minimization (NLARM) problem. For this problem, we derive explicit bounds on the sample complexity as well as running time of our approach, and show that it achieves the best possible bounds for both cases. We also support our proposed algorithm via several experimental results.

    Original languageEnglish (US)
    Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages371-375
    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 'Fast Low-Rank Matrix Estimation for Ill-Conditioned Matrices'. Together they form a unique fingerprint.

    Cite this