On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem
On Sampling Complexity of the Semidefinite Affine Rank Feasibility Problem
复制标题
DOI：
10.1609/aaai.v33i01.33011568
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Igor Molybog;J. Lavaei
中科院分区：
文献类型：
--
作者：
Igor Molybog;J. Lavaei
本文研究了半定仿射秩可行性问题，即由矩阵的线性度量求给定秩的半正定矩阵。我们考虑了具有不同目标函数的半定规划松弛问题，并研究了它们的性质。特别是，我们提出了一个分析界的松弛，足以解决，以获得解决方案的半定仿射秩可行性问题的一般情况下，或证明没有解决方案的数量。其次是一个启发式算法的基础上半定松弛和实验证明其性能的大样本的合成数据。
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.