Column Bound for Orthogonal Matrix Factorization
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911883360993280 |
|---|---|
| author | Dash, Anirudh |
| author_facet | Dash, Anirudh |
| contents | This article explores the intersection of the Coupon Collector's Problem and the Orthogonal Matrix Factorization (OMF) problem. Specifically, we derive bounds on the minimum number of columns $p$ (in $\mathbf{X}$) required for the OMF problem to be tractable, using insights from the Coupon Collector's Problem. Specifically, we establish a theorem outlining the relationship between the sparsity of the matrix $\mathbf{X}$ and the number of columns $p$ required to recover the matrices $\mathbf{V}$ and $\mathbf{X}$ in the OMF problem. We show that the minimum number of columns $p$ required is given by $p = Ω\left(\max \left\{ \frac{n}{1 - (1 - θ)^n}, \frac{1}θ \log n \right\} \right)$, where $θ$ is the i.i.d Bernoulli parameter from which the sparsity model of the matrix $\mathbf{X}$ is derived. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12858 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Column Bound for Orthogonal Matrix Factorization Dash, Anirudh Signal Processing This article explores the intersection of the Coupon Collector's Problem and the Orthogonal Matrix Factorization (OMF) problem. Specifically, we derive bounds on the minimum number of columns $p$ (in $\mathbf{X}$) required for the OMF problem to be tractable, using insights from the Coupon Collector's Problem. Specifically, we establish a theorem outlining the relationship between the sparsity of the matrix $\mathbf{X}$ and the number of columns $p$ required to recover the matrices $\mathbf{V}$ and $\mathbf{X}$ in the OMF problem. We show that the minimum number of columns $p$ required is given by $p = Ω\left(\max \left\{ \frac{n}{1 - (1 - θ)^n}, \frac{1}θ \log n \right\} \right)$, where $θ$ is the i.i.d Bernoulli parameter from which the sparsity model of the matrix $\mathbf{X}$ is derived. |
| title | Column Bound for Orthogonal Matrix Factorization |
| topic | Signal Processing |
| url | https://arxiv.org/abs/2405.12858 |