Column Bound for Orthogonal Matrix Factorization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |