论文标题
一些算法，用于最大体积和对称半矩阵的交叉近似
Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
论文作者
论文摘要
查找矩阵$ a \ in \ mathbb r^{n \ times n} $的最大体积的$ r \ times r $ ubsatrix是在多种应用中出现的NP硬问题。我们提出了一种新的贪婪算法，成本$ \ MATHCAL O（n）$，对于$ a $ a $对称的正阳性半菲斯（SPSD），我们讨论了其扩展到相关优化问题的扩展，例如最大体积比率。在本文的第二部分中，我们证明，任何SPSD矩阵都承认在主要的cobsatrix上构建的交叉近似，其近似错误的限制为$（r+1）$乘以核定标准中最佳等级$ r $近似值的误差。本着Cortinovis和Kressner最近工作的精神，我们得出了一些确定性算法，这些算法能够以$ \ Mathcal o（n^3）$来检索准最佳交叉近似。
Finding the $r\times r$ submatrix of maximum volume of a matrix $A\in\mathbb R^{n\times n}$ is an NP hard problem that arises in a variety of applications. We propose a new greedy algorithm of cost $\mathcal O(n)$, for the case $A$ symmetric positive semidefinite (SPSD) and we discuss its extension to related optimization problems such as the maximum ratio of volumes. In the second part of the paper we prove that any SPSD matrix admits a cross approximation built on a principal submatrix whose approximation error is bounded by $(r+1)$ times the error of the best rank $r$ approximation in the nuclear norm. In the spirit of recent work by Cortinovis and Kressner we derive some deterministic algorithms which are capable to retrieve a quasi optimal cross approximation with cost $\mathcal O(n^3)$.
