Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2411.16101 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912231148486656 |
|---|---|
| author | Shah, Rikhav Detherage, Isabel |
| author_facet | Shah, Rikhav Detherage, Isabel |
| contents | This paper asks if the following iterative procedure approximately orthogonalizes a set of $n$ linearly independent unit vectors while preserving their span: in each iteration, access a random pair of vectors and replace one with the component perpendicular to the other, renormalized to be a unit vector.
We provide a positive answer: any given set of starting vectors converges almost surely to an orthonormal basis of their span. We specifically argue that the $n$-volume of the parallelepiped generated by the vectors approaches 1 (i.e. the parallelepiped approaches a hypercube). If $A$ is the matrix formed by taking these vectors as columns, this volume is simply $\det(|A|)$ where $|A|=(A^*A)^{1/2}$. We show that $O(n^2\log(1/(\det(|A|)\varepsilon)))$ iterations suffice to bring ${\det(|A|)}$ above $1-\varepsilon$ with constant probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16101 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Kaczmarz-Inspired Method for Orthogonalization Shah, Rikhav Detherage, Isabel Probability 65F25, 15A12, 60 This paper asks if the following iterative procedure approximately orthogonalizes a set of $n$ linearly independent unit vectors while preserving their span: in each iteration, access a random pair of vectors and replace one with the component perpendicular to the other, renormalized to be a unit vector. We provide a positive answer: any given set of starting vectors converges almost surely to an orthonormal basis of their span. We specifically argue that the $n$-volume of the parallelepiped generated by the vectors approaches 1 (i.e. the parallelepiped approaches a hypercube). If $A$ is the matrix formed by taking these vectors as columns, this volume is simply $\det(|A|)$ where $|A|=(A^*A)^{1/2}$. We show that $O(n^2\log(1/(\det(|A|)\varepsilon)))$ iterations suffice to bring ${\det(|A|)}$ above $1-\varepsilon$ with constant probability. |
| title | A Kaczmarz-Inspired Method for Orthogonalization |
| topic | Probability 65F25, 15A12, 60 |
| url | https://arxiv.org/abs/2411.16101 |