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.
Cite
Text
Molybog and Lavaei. "On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011568Markdown
[Molybog and Lavaei. "On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/molybog2019aaai-sampling/) doi:10.1609/AAAI.V33I01.33011568BibTeX
@inproceedings{molybog2019aaai-sampling,
title = {{On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem}},
author = {Molybog, Igor and Lavaei, Javad},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {1568-1575},
doi = {10.1609/AAAI.V33I01.33011568},
url = {https://mlanthology.org/aaai/2019/molybog2019aaai-sampling/}
}