Role of sparsity and structure in the optimization landscape of non-convex matrix sensing

• 成果类型: Article
• 署名作者: Molybog, Igor; Sojoudi, Somayeh; Lavaei, Javad
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01590-2
• 发表日期: 2022
• 页码: 75-111
• 关键词: completion

摘要

In this work, we study the optimization landscape of the non-convex matrix sensing problem that is known to have many local minima in the worst case. Since the existing results are related to the notion of restricted isometry property (RIP) that cannot directly capture the underlying structure of a given problem, they can hardly be applied to real-world problems where the amount of data is not exorbitantly high. To address this issue, we develop the notion of kernel structure property to obtain necessary and sufficient conditions for the inexistence of spurious local solutions for any class of matrix sensing problems over a given search space. This notion precisely captures the underlying sparsity and structure of the problem, based on tools in conic optimization. We simplify the conditions for a certain class of problems to show their satisfaction and apply them to data analytics for power systems.