Fast Low-Rank Matrix Estimation for Ill-Conditioned Matrices

Mohammadreza Soltani, Chinmay Hegde

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


    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.
    Number of pages5
    ISBN (Print)9781538647806
    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
    ISSN (Print)2157-8095


    Other2018 IEEE International Symposium on Information Theory, ISIT 2018
    Country/TerritoryUnited States

    ASJC Scopus subject areas

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


    Dive into the research topics of 'Fast Low-Rank Matrix Estimation for Ill-Conditioned Matrices'. Together they form a unique fingerprint.

    Cite this