New Lower Bounds for the Minimum Singular Value in Matrix Selection

The objective of the matrix selection problem is to select a submatrix $A_{S}\in \mathbb{R}^{n\times k}$ from $A\in \mathbb{R}^{n\times m}$ such that its minimum singular value is maximized. In this paper, we employ the interlacing polynomial method to investigate this problem. This approach allows us to identify a submatrix $A_{S_0}\in \mathbb{R}^{n\times k}$ and establish a lower bound for its minimum singular value. Specifically, unlike common interlacing polynomial approaches that estimate the smallest root of the expected characteristic polynomial via barrier functions, we leverage the direct relationship between roots and coefficients. This leads to a tighter lower bound when $k$ is close to $n$. For the case where $AA^{\top}=\mathbb{I}_n$ and $k=n$, our result improves the well-known result by Hong-Pan, which involves extracting a basis from a tight frame and establishing a lower bound for the minimum singular value of the basis matrix.