Polynomial time algorithms provide efficient Kadison-Singer problem solutions
Polynomial Time Algorithms for the Kadison-Singer Problem
Data Structures and Algorithms
Summary
The Kadison-Singer problem is a long-standing question in mathematics about how certain matrices or vectors can be split into smaller parts while keeping their properties balanced. Previously, it was only known that such partitions exist, but no practical way to find them efficiently. The authors develop new algorithms that can quickly (in polynomial time) find these balanced partitions for specific types of matrices and vectors. These algorithms come in two flavors: one deterministic and one randomized, each with trade-offs in speed and accuracy.
What this means in practice
- •For signal processing engineers: Build algorithms that split signals or vectors into balanced components efficiently for improved stability and performance.
- •For numerical linear algebra developers: Implement faster methods for matrix partitioning tasks that require preserving spectral properties in scientific computing.
Authors
Zhao Song, Song Yue
Abstract
Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $σ\in\{\pm1\}^m$ satisfying $\|\sum_i σ_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{56})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{5.88})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\leα$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrtα$ for $j=1,2$.