Role of Sparsity and Structure in the Optimization Landscape of Non-convex Matrix Sensing

Igor Molybog, Somayeh Sojoudi, and Javad Lavaei, Role of Sparsity and Structure in the Optimization Landscape of Non-convex Matrix Sensing, to appear in Mathematical Programming, 2020.

Abstract: 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 solution of 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.