On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem

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.