Computing the Moore-Penrose inverse for bidiagonal matrices
Loading...
Date
2019
Authors
Hakopian, Yuri
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The Moore-Penrose inverse is the most popular type of matrix generalized inverses which has many applications both in matrix theory and numerical linear algebra. It is well known that the Moore-Penrose inverse can be found via singular value decomposition. In this regard, there is the most effective algorithm which consists of two stages. In the first stage, through the use of the Householder reflections, an initial matrix is reduced to the upper bidiagonal form (the Golub-Kahan bidiagonalization algorithm). The second stage is known in scientific literature as the Golub-Reinsch algorithm. This is an iterative procedure which with the help of the Givens rotations generates a sequence of bidiagonal matrices converging to a diagonal form. This allows to obtain an iterative approximation to the singular value decomposition of the bidiagonal matrix.
The principal intention of the present paper is to develop a method which can be considered as an alternative to the Golub-Reinsch iterative algorithm. Realizing the approach proposed in the study, the following two main results have been achieved. First, we obtain explicit expressions for the entries of the Moore-Penrose inverse of bidigonal matrices. Secondly, based on the closed form formulas, we get a finite recursive numerical algorithm of optimal computational complexity. Thus, we can compute the Moore-Penrose inverse of bidiagonal matrices without using the singular value decomposition.
Обернене вiдображення Мура–Пенроуза є найбiльш поширеним вiдображенням, що використовується для пошуку оберненої матрицi. Це вiдображення має численнi застосування як у теорiї матриць, так i в обчислювальнiй лiнiйнiй алгебрi. Вiдомо, що обернена матриця Мура–Пенроуза може бути отримана через сингулярний розклад. Найефективнiший з iснуючих алгоритмiв складається з двох крокiв. На першому кроцi, використовуючи вiдображення Хаусхолдера, початкова матриця зводиться до верхнього двудiагонального вигляду (алгоритм Голуба–Кахана). Другий крок вiдомий у науковiй лiтературi як алгоритм Голуба–Райнша. Ця iтерацiйна процедура за допомогою методу Гiвенса генерує послiдовнiсть двудiагональних матриць, яка збiгається до дiагонального вигляду. В такий спосiб отримується iтерацiйне наближення до сингулярного розкладу двудiагональної матрицi. Головною метою цiєї статтi є розробка методу, який можна розглядати як альтернативну замiну алгоритму Голуба–Райнша. За допомогою реалiзацiї запропонованого, було отримано два головнi результати. По-перше, виведено явнi формули для елементiв обернених матриць Мура–Пенроуза для двудiагональних матриць. По-друге, використовуючи цi формули, побудовано скiнченний рекурсивний алгоритм, оптимальної обчислювальної складностi. Таким чином, запропоновано варiант обчислення оберненої матрицi Мура–Пенроуза для двудiагональних матриць, що не використовує сингулярний розклад.
Обернене вiдображення Мура–Пенроуза є найбiльш поширеним вiдображенням, що використовується для пошуку оберненої матрицi. Це вiдображення має численнi застосування як у теорiї матриць, так i в обчислювальнiй лiнiйнiй алгебрi. Вiдомо, що обернена матриця Мура–Пенроуза може бути отримана через сингулярний розклад. Найефективнiший з iснуючих алгоритмiв складається з двох крокiв. На першому кроцi, використовуючи вiдображення Хаусхолдера, початкова матриця зводиться до верхнього двудiагонального вигляду (алгоритм Голуба–Кахана). Другий крок вiдомий у науковiй лiтературi як алгоритм Голуба–Райнша. Ця iтерацiйна процедура за допомогою методу Гiвенса генерує послiдовнiсть двудiагональних матриць, яка збiгається до дiагонального вигляду. В такий спосiб отримується iтерацiйне наближення до сингулярного розкладу двудiагональної матрицi. Головною метою цiєї статтi є розробка методу, який можна розглядати як альтернативну замiну алгоритму Голуба–Райнша. За допомогою реалiзацiї запропонованого, було отримано два головнi результати. По-перше, виведено явнi формули для елементiв обернених матриць Мура–Пенроуза для двудiагональних матриць. По-друге, використовуючи цi формули, побудовано скiнченний рекурсивний алгоритм, оптимальної обчислювальної складностi. Таким чином, запропоновано варiант обчислення оберненої матрицi Мура–Пенроуза для двудiагональних матриць, що не використовує сингулярний розклад.
Description
Keywords
Moor-Penrose inverse, bidiagonal matrix, inversion formula, finite recursive algorithm, article, псевдообернення Мура–Пенроуза, двудiагональна матриця, формула обернення, рекурсивний алгоритм, стаття
Citation
Hakopian Yu. Computing the Moore-Penrose inverse for bidiagonal matrices / Yuri Hakopian // Могилянський математичний журнал. - 2019. - Т. 2. - С. 11-23.