{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129360"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129360","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Over-parameterized low-rank matrix estimation: Theory, algorithms, applications","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_has_math":false,"creators":["Zhang, Jialun"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Zhang, Richard","Raginsky, Maxim","Zhao, Zhizhen","Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-20","date_published":"2025-04-20","updated_at":"2026-07-22T22:25:05Z","subjects":["low-rank matrix recovery","nonconvex optimization","mathematical optimization"],"languages":["en","eng"],"rights":["Copyright 2025 Jialun Zhang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129360","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Zhang, Richard","Raginsky, Maxim","Zhao, Zhizhen","Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Zhang, Jialun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-20","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["low-rank matrix recovery","nonconvex optimization","mathematical optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Jialun Zhang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129360"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Jialun Zhang, accepted the attached license on 2025-04-14 at 01:48.","The student, Jialun Zhang, submitted this Dissertation for approval on 2025-04-14 at 01:53.","This Dissertation was approved for publication on 2025-04-20 at 16:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21599 on 2025-10-19 at 18:17:12","This thesis considers the non-convex methods for low-rank matrix estimation based on Burer-Monteiro factorization, which offers better scalability and lower per-iteration costs compared to convex methods. However, non-convex optimization faces challenges from spurious local minima or critical points, which can lead gradient-based algorithms to converge to suboptimal solutions. Prior research has shown that a sufficiently large training dataset can eliminate spurious minima in non-convex problems, enabling successful low-rank estimation. However, these guarantees are often impractical in real-world applications for two reasons. First, they require a large amount of data to remove spurious local minima across the entire parameter space, which is costly and challenging for large-scale applications. Second, they assume ``regular\" measurement conditions (e.g., restricted isometry property or incoherence), which are rarely satisfied in practice. To address these challenges, we first prove that a good initial point can reduce the required sample size to avoid spurious minima near the ground truth. This insight reveals that practical low-rank estimation problems are often less demanding in terms of data than prior theory suggests. Specifically, there is a direct tradeoff: better initial point quality linearly reduces sample complexity, and vice versa. The thesis thus sheds light on how non-convex landscapes become more manageable with improved initialization or increased samples, providing insights that could extend to other non-convex problems. The major focus of our thesis is how over-parameterization can be used to effectively solve non-convex matrix estimation problems. Over-parameterization serves two purposes: it certifies global optimality by allowing sufficient flexibility in the model, and it ensures solution accuracy even when the true rank $r^*$ is hard to estimate. Unfortunately, over-parameterization slows gradient descent exponentially, which dramatically increases the cost to converge to the ground truth. To overcome this, the thesis introduces PrecGD (preconditioned gradient descent), a method that preserves the fast convergence of gradient descent, achieving exponential error reduction per iteration. PrecGD’s convergence rate is independent of ill-conditioning or over-parameterization, with a per-iteration cost only slightly higher than standard gradient descent. Finally, we also extend our algorithm, PrecGD, to two important practical settings: (1) first, we present a stochastic version of PrecGD that applies even to huge-scale matrix completion type problems where even on full-batch gradient evaluation is too expensive. (2) Then, we consider adapting our algorithm to scenarios where the measurements are extremely noisy, which makes preconditioning significantly more difficult since it is easy to magnify the noise as well. In both cases we present a rigorous proof for the success of our method, which is also validated extensively in numerical experiments."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Over-parameterized low-rank matrix estimation: Theory, algorithms, applications"]}]}],"canonical_facts":{"dc:contributor":["Zhang, Richard","Raginsky, Maxim","Zhao, Zhizhen","Srikant, Rayadurgam"],"dc:creator":["Zhang, Jialun"],"dc:date":["2025-04-20","2025-05"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Jialun Zhang, accepted the attached license on 2025-04-14 at 01:48.","The student, Jialun Zhang, submitted this Dissertation for approval on 2025-04-14 at 01:53.","This Dissertation was approved for publication on 2025-04-20 at 16:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21599 on 2025-10-19 at 18:17:12","This thesis considers the non-convex methods for low-rank matrix estimation based on Burer-Monteiro factorization, which offers better scalability and lower per-iteration costs compared to convex methods. However, non-convex optimization faces challenges from spurious local minima or critical points, which can lead gradient-based algorithms to converge to suboptimal solutions. Prior research has shown that a sufficiently large training dataset can eliminate spurious minima in non-convex problems, enabling successful low-rank estimation. However, these guarantees are often impractical in real-world applications for two reasons. First, they require a large amount of data to remove spurious local minima across the entire parameter space, which is costly and challenging for large-scale applications. Second, they assume ``regular\" measurement conditions (e.g., restricted isometry property or incoherence), which are rarely satisfied in practice. To address these challenges, we first prove that a good initial point can reduce the required sample size to avoid spurious minima near the ground truth. This insight reveals that practical low-rank estimation problems are often less demanding in terms of data than prior theory suggests. Specifically, there is a direct tradeoff: better initial point quality linearly reduces sample complexity, and vice versa. The thesis thus sheds light on how non-convex landscapes become more manageable with improved initialization or increased samples, providing insights that could extend to other non-convex problems. The major focus of our thesis is how over-parameterization can be used to effectively solve non-convex matrix estimation problems. Over-parameterization serves two purposes: it certifies global optimality by allowing sufficient flexibility in the model, and it ensures solution accuracy even when the true rank $r^*$ is hard to estimate. Unfortunately, over-parameterization slows gradient descent exponentially, which dramatically increases the cost to converge to the ground truth. To overcome this, the thesis introduces PrecGD (preconditioned gradient descent), a method that preserves the fast convergence of gradient descent, achieving exponential error reduction per iteration. PrecGD’s convergence rate is independent of ill-conditioning or over-parameterization, with a per-iteration cost only slightly higher than standard gradient descent. Finally, we also extend our algorithm, PrecGD, to two important practical settings: (1) first, we present a stochastic version of PrecGD that applies even to huge-scale matrix completion type problems where even on full-batch gradient evaluation is too expensive. (2) Then, we consider adapting our algorithm to scenarios where the measurements are extremely noisy, which makes preconditioning significantly more difficult since it is easy to magnify the noise as well. In both cases we present a rigorous proof for the success of our method, which is also validated extensively in numerical experiments."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129360"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Jialun Zhang"],"dc:subject":["low-rank matrix recovery","nonconvex optimization","mathematical optimization"],"dc:title":["Over-parameterized low-rank matrix estimation: Theory, algorithms, applications"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:05Z"}