On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem

Authors

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

DOI:

https://doi.org/10.1609/aaai.v33i01.33011568

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.

Downloads

Published

2019-07-17

How to Cite

Molybog, I., & Lavaei, J. (2019). On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1568-1575. https://doi.org/10.1609/aaai.v33i01.33011568

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization