Turing meets Moore-Penrose: Computing the Pseudoinverse on Turing Machines
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912832299204608 |
|---|---|
| author | Boche, Holger Fono, Adalbert Kutyniok, Gitta |
| author_facet | Boche, Holger Fono, Adalbert Kutyniok, Gitta |
| contents | The pseudoinverse of a matrix, a generalized notion of the inverse, is of fundamental importance in linear algebra and, thereby, in many different fields. Despite its proven existence, an algorithmic approach is typically necessary to obtain the pseudoinverse in practical applications. Therefore, we analyze if and to what degree the pseudoinverse can be computed on perfect digital hardware platforms modeled as Turing machines. For this, we utilize the notion of an effective algorithm that describes a provably correct computation: upon an input of any error parameter, the algorithm provides an approximation within the given error bound with respect to the unknown solution. We prove that a universal effective algorithm for computing the pseudoinverse of any matrix with a finite error bound does not exist on Turing machines. However, for specific classes of matrices, we show that provably correct algorithms exist and obtain a characterization of the properties of the input set, leading to the effective computability breakdown. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_02940 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Turing meets Moore-Penrose: Computing the Pseudoinverse on Turing Machines Boche, Holger Fono, Adalbert Kutyniok, Gitta Numerical Analysis The pseudoinverse of a matrix, a generalized notion of the inverse, is of fundamental importance in linear algebra and, thereby, in many different fields. Despite its proven existence, an algorithmic approach is typically necessary to obtain the pseudoinverse in practical applications. Therefore, we analyze if and to what degree the pseudoinverse can be computed on perfect digital hardware platforms modeled as Turing machines. For this, we utilize the notion of an effective algorithm that describes a provably correct computation: upon an input of any error parameter, the algorithm provides an approximation within the given error bound with respect to the unknown solution. We prove that a universal effective algorithm for computing the pseudoinverse of any matrix with a finite error bound does not exist on Turing machines. However, for specific classes of matrices, we show that provably correct algorithms exist and obtain a characterization of the properties of the input set, leading to the effective computability breakdown. |
| title | Turing meets Moore-Penrose: Computing the Pseudoinverse on Turing Machines |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2212.02940 |