Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914789118181376 |
|---|---|
| author | Guruswami, Venkatesan Hsieh, Jun-Ting Raghavendra, Prasad |
| author_facet | Guruswami, Venkatesan Hsieh, Jun-Ting Raghavendra, Prasad |
| contents | We consider the task of certifying that a random $d$-dimensional subspace $X$ in $\mathbb{R}^n$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$. In a seminal work, Barak et. al. showed a polynomial-time certification algorithm when $d \leq O(\sqrt{n})$. On the other hand, when $d \gg \sqrt{n}$, the certification task is information-theoretically possible but there is evidence that it is computationally hard [MW21,Cd22], a phenomenon known as the information-computation gap.
In this paper, we give subexponential-time certification algorithms in the $d \gg \sqrt{n}$ regime. Our algorithm runs in time $\exp(\widetilde{O}(n^{\varepsilon}))$ when $d \leq \widetilde{O}(n^{(1+\varepsilon)/2})$, establishing a smooth trade-off between runtime and the dimension.
Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05373 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold Guruswami, Venkatesan Hsieh, Jun-Ting Raghavendra, Prasad Data Structures and Algorithms Computational Complexity Metric Geometry We consider the task of certifying that a random $d$-dimensional subspace $X$ in $\mathbb{R}^n$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$. In a seminal work, Barak et. al. showed a polynomial-time certification algorithm when $d \leq O(\sqrt{n})$. On the other hand, when $d \gg \sqrt{n}$, the certification task is information-theoretically possible but there is evidence that it is computationally hard [MW21,Cd22], a phenomenon known as the information-computation gap. In this paper, we give subexponential-time certification algorithms in the $d \gg \sqrt{n}$ regime. Our algorithm runs in time $\exp(\widetilde{O}(n^{\varepsilon}))$ when $d \leq \widetilde{O}(n^{(1+\varepsilon)/2})$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task. |
| title | Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold |
| topic | Data Structures and Algorithms Computational Complexity Metric Geometry |
| url | https://arxiv.org/abs/2405.05373 |