Ziye Ma

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-18

April 24, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-18.pdf

Matrix sensing represents a critical, non-convex challenge within the domain of mathematical optimization, distinguished by its wide-ranging practical applications—such as medical imaging, recommender systems, and phase retrieval—as well as its significant theoretical contributions, particularly its equivalence to training a two-layer quadratic neural network. The ability to efficiently solve this problem to optimality promises substantial benefits not only for its direct applications but also provides a crucial benchmark that aids in navigating the increasingly intricate non-convex landscapes characteristic of contemporary machine learning systems. While prior research predominantly focuses on scenarios abundant in observations and characterized by a low Restricted Isometry Property (RIP) constant, thereby facilitating optimal solutions through either convex relaxation methods, including nuclear-norm minimization, or local search strategies applied to the Burer-Monteiro factorized formulation—thereby accelerating computational processes without compromising performance guarantees—the research to date remains incomplete. This is particularly true in real-world settings where acquiring a large volume of observations is often impractical, thus rendering these guarantees inapplicable.

In this dissertation, we propose innovative strategies, models, and conceptual frameworks aimed at addressing the matrix sensing problem under conditions of limited observations and noise corruptions, with the objective of provably reconstructing the ground truth matrix. Our discussion begins by exploring various methodologies of over-parametrization as a means to solve this problem, followed by an examination of alternative solutions in scenarios where over-parametrization is not used. Additionally, we delve into the impact of noise on the extraction of a global solution, offering insights into how it affects the overall process. This work serves not only as an elaborate guide to resolving matrix sensing and, by extension, low-rank optimization problems in less than ideal conditions but also endeavors to enhance our understanding of the complexities involved in non-convex optimization, thereby contributing to the broader field of mathematical optimization and machine learning.

Advisors: Somayeh Sojoudi

---

BibTeX citation:

@phdthesis{Ma:EECS-2024-18,
    Author= {Ma, Ziye},
    Title= {Solving Matrix Sensing to Optimality under Realistic Settings},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-18.html},
    Number= {UCB/EECS-2024-18},
    Abstract= {Matrix sensing represents a critical, non-convex challenge within the domain of mathematical optimization, distinguished by its wide-ranging practical applications—such as medical imaging, recommender systems, and phase retrieval—as well as its significant theoretical contributions, particularly its equivalence to training a two-layer quadratic neural network. The ability to efficiently solve this problem to optimality promises substantial benefits not only for its direct applications but also provides a crucial benchmark that aids in navigating the increasingly intricate non-convex landscapes characteristic of contemporary machine learning systems. While prior research predominantly focuses on scenarios abundant in observations and characterized by a low Restricted Isometry Property (RIP) constant, thereby facilitating optimal solutions through either convex relaxation methods, including nuclear-norm minimization, or local search strategies applied to the Burer-Monteiro factorized formulation—thereby accelerating computational processes without compromising performance guarantees—the research to date remains incomplete. This is particularly true in real-world settings where acquiring a large volume of observations is often impractical, thus rendering these guarantees inapplicable.

In this dissertation, we propose innovative strategies, models, and conceptual frameworks aimed at addressing the matrix sensing problem under conditions of limited observations and noise corruptions, with the objective of provably reconstructing the ground truth matrix. Our discussion begins by exploring various methodologies of over-parametrization as a means to solve this problem, followed by an examination of alternative solutions in scenarios where over-parametrization is not used. Additionally, we delve into the impact of noise on the extraction of a global solution, offering insights into how it affects the overall process. This work serves not only as an elaborate guide to resolving matrix sensing and, by extension, low-rank optimization problems in less than ideal conditions but also endeavors to enhance our understanding of the complexities involved in non-convex optimization, thereby contributing to the broader field of mathematical optimization and machine learning.},
}

EndNote citation:

%0 Thesis
%A Ma, Ziye 
%T Solving Matrix Sensing to Optimality under Realistic Settings
%I EECS Department, University of California, Berkeley
%D 2024
%8 April 24
%@ UCB/EECS-2024-18
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-18.html
%F Ma:EECS-2024-18