On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem

  • Igor Molybog University of California, Berkeley
  • Javad Lavaei University of California, Berkeley

Abstract

In this paper, we study the semidefinite affine rank feasibility problem, which consists in finding a positive semidefinite matrix of a given rank from its linear measurements. We consider the semidefinite programming relaxations of the problem with different objective functions and study their properties. In particular, we propose an analytical bound on the number of relaxations that are sufficient to solve in order to obtain a solution of a generic instance of the semidefinite affine rank feasibility problem or prove that there is no solution. This is followed by a heuristic algorithm based on semidefinite relaxation and an experimental proof of its performance on a large sample of synthetic data.

Published
2019-07-17
Section
AAAI Technical Track: Constraint Satisfaction and Optimization