New Lower Bounds for the Minimum Singular Value in Matrix Selection
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913991335346176 |
|---|---|
| author | Xu, Zhiqiang |
| author_facet | Xu, Zhiqiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10452 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Lower Bounds for the Minimum Singular Value in Matrix Selection Xu, Zhiqiang Functional Analysis Numerical Analysis 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. |
| title | New Lower Bounds for the Minimum Singular Value in Matrix Selection |
| topic | Functional Analysis Numerical Analysis |
| url | https://arxiv.org/abs/2508.10452 |