On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem

Igor Molybog, Javad LavaeiAAAI 2019 · DOI

Introduction

The Semidefinite Affine Rank Feasibility (SARF) problem is a fundamental challenge in modern data science, underpinning applications ranging from the "Netflix Prize" matrix completion to medical phase retrieval and power grid state estimation. The core task is to find a low-rank, positive semidefinite (PSD) matrix that satisfies a set of linear observations. Because the rank constraint is inherently non-convex, the problem is generally NP-hard. This paper, presented at AAAI-19, explores the theoretical and practical boundaries of solving SARF without relying on the restrictive "Restricted Isometry Property" (RIP) often assumed in compressed sensing.

Methodology: SDP Relaxations and Recovery Regions

To circumvent the NP-hardness of the rank constraint, the authors employ a series of convex Semidefinite Programming (SDP) relaxations. Instead of solving for rank directly, they solve optimization problems with varying linear objective functions $\langle N, X \rangle$.

A central concept in their analysis is the recovery region of an objective matrix $N$. This is defined as the set of all rank-$k$ matrices that can be uniquely recovered by solving an SDP with $N$ as the objective. By utilizing differential geometry and "covering numbers" on the Stiefel manifold, the authors calculate the number of distinct objective matrices required to ensure that their combined recovery regions cover the entire space of possible solutions.

Visualization of the geometric complexity of recovery regions in the parameter space.

The Complexity Phase Transition

The paper's most significant insight is the identification of a "phase transition" in the problem's solvability. For generic instances where the number of measurements $m$ exceeds the threshold $k(2n-k)$, the problem becomes solvable with a finite number of SDPs.

Empirically, the authors demonstrate that as the number of available measurements increases beyond the theoretical minimum, the probability of a single randomized SDP finding the correct low-rank solution jumps from 0% to nearly 100% very rapidly. This S-curve behavior suggests that while the general problem is hard, many practical instances fall into a regime where they are efficiently solvable.

Key Results and Empirical Validation

The authors derived an explicit analytical upper bound for the number of SDP relaxations needed, providing a mathematical "ceiling" for a problem previously considered potentially intractable. Furthermore, they proved a polynomial-time corollary: if the number of measurements $m$ grows at a rate of $O(n^2)$, the problem effectively becomes solvable in polynomial time for generic instances.

Numerical experiments using synthetic data (with dimensions $n=15, 20, 25$) confirmed these theoretical predictions. As shown in the success frequency plots, the transition to guaranteed recovery is consistent across different matrix sizes and ranks.

Success frequency of the randomized heuristic across different matrix dimensions (n) and ranks (k), illustrating the phase transition.

Conclusion and Future Work

By focusing on the manifold geometry of low-rank matrices rather than RIP conditions, this work provides a new framework for understanding matrix feasibility. While the current analytical bounds remain exponential relative to matrix dimensions, they offer a rigorous foundation for future research. Ongoing work aims to address noise sensitivity and investigate how specific physical structures—such as those found in power grid topologies—might lead to even tighter, non-exponential complexity bounds.

Summary updated

BibTeX
@inproceedings{molybog2019sampling,
  author = {Igor Molybog and Javad Lavaei},
  title = {{On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011568},
}
Figure