Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования

Abstract

Одним з найбільш ефективних і найбільш простих в обчислювальному відношенні однокрокових алгоритмів оцінювання є алгоритм Качмажа, запропонований в [1]. У багатьох подальших роботах було розглянуто можливість прискорення алгоритму Качмажа шляхом використання не одного, а ряду вимірювань. Роботи [8, 9] послужили поштовхом до розробки нового класу багатокрокових проекційних алгоритмів [10–14], в яких при побудові оцінки на n-му кроці використовується не тільки нова інформація, як це відбувається в алгоритмі Качмажа, а й інформація про ряд попередніх кроків n – 1, n – 2 .... . Кількість таких кроків визначає пам’ять алгоритму. При цьому завдяки кращій екстраполяції і фільтрації у ряді випадків вдається домогтися істотного скорочення часу ідентифікації. Реалізація багатокрокового (S-крокового) проекційного алгоритму вимагає обчислення зворотної матриці спостережень розмірності S  S. В [11–14] встановлено властивості випадкових псевдообернених матриць і матриць проеційованих, які дозволили визначити швидкість збіжності даних алгоритмів і зробити висновок про те, що урахування в даних алгоритмах інформації про S попередніх кроків рівносильне в сенсі швидкості збіжності зменшенню розмірності вихідного простору N на S. У даній роботі пропонуються і досліджуються псевдопроекційні алгоритми, що володіють близькими до багатокрокових проекційних алгоритмів властивостями, але більш прості в реалізації. Дані алгоритми використовують апроксимацію операції точного проеціювання і будуються на основі однокрокового адаптивного алгоритму Качмажа. Отримано оцінки швидкості збіжності запропонованих процедур і показано, що використання такої апроксимації дозволяє при незначному зниженні швидкості збіжності алгоритмів істотно спростити їх реалізацію та підвищити обчислювальну стійкість внаслідок усунення операції обертання матриці спостережень.

Kaczmarz algorithm proposed in [1] is one of the most effective and most computationally simple one-step estimation algorithms. In a number of subsequent studies the possibility of acceleration algorithm Kaczmarz by the use of not one but a series of measurements was examined. Research made in [8, 9] was a push for the development of a new class of algorithms — multistage projection algorithms [10–14], in which during the construction of estimates on the n-th step not only new information is used, as it comes in Kaczmarz algorithm, but also information about number of previous steps n–1, n–2 .... . The number of these steps determines the algorithm’s memory. In this case, thanks to a better extrapolation and filtering, in some cases it is possible to reduce significantly the time of identification. The implementation of multi-step ( S -step) projection algorithm requires the computation of the inverse matrix of observations with S  S dimension. In [11–14] properties of random pseudoinverse matrix and the projection matrix are set. It helped to determine the rate of convergence of these algorithms and conclude that taking into account information about previous S steps is equivalent in terms of convergence speed to reduction of dimension N in the original space to S. In this paper we propose and investigate pseudoprojective algorithms that have close to the multi-stage projection algorithm properties, but are simpler to implement. These algorithms use an approximation of the exact projection operation and are based on one-step Kaczmarz adaptive algorithm. Estimates of the convergence rate of the proposed procedures are obtained. It is shown that the use of such approximation allows, with a slight decrease in the convergence rate of the algorithms, to simplify significantly their implementation and increase computational stability due to eliminating the rotation operation of the observation matrix.