Максимально разреженное представление ортогональной матрицы

[zgemm]

Добрый день,

пусть у меня есть $v \in {\callBB R}^n$, $||v||_2=1$, и я хочу построить $Q \in {\calBB R}^{n \times n-1}, ~~ Q^T v = 0, ~~ Q^T Q = 0$, но я хочу сделать так, что $Q$ будет содержать очень много нулей. Сколько максимум этих нулей можно там получить? Я смог получить по построению всреднем $\log_2 n$ нулей на строку, для этого я взял исходный вектор $v$, разбил по два, и взял с разным знаком, то есть

$$\left(\begin{tabular}{ccccccccccc} $v_1$ & $v_1$ & $0$ & $0$ & $\dots$ & $0$ & $0$ & $a_1 v_1$ & $\dots$ & $0$ & $\dots$ \\ $v_2$ & $-v_2$ & $0$ & $0$ & $\dots$ & $0$ & $0$ & $a_1 v_2$ & $\dots$ & $0$ & $\dots$ \\ $v_3$ & $0$ & $v_3$ & $0$ & $\dots$ & $0$ & $0$ & $a_2 v_3$ & $\dots$ & $0$ & $\dots$ \\ $v_4$ & $0$ & $v_4$ & $0$ & $\dots$ & $0$ & $0$ & $a_2 v_4$ & $\dots$ & $0$ & $\dots$ \\ $\vdots$ & $0$ & $0$ & $0$ & $\vdots$ & $0$ & $0$ & $0$ & $\vdots$ & $0$ & $\vdots$ \\ $v_{n-3}$ & $0$ & $0$ & $\dots$ & $0$ & $v_{n-3}$ & $0$ & $0$ & $\dots$ & $a_{n/2-1} v_{n-3}$ & $\dots$ \\ $v_{n-2}$ & $0$ & $0$ & $\dots$ & $0$ & $-v_{n-2}$ & $0$ & $0$ & $\dots$ & $a_{n/2-1} v_{n-2}$ & $\dots$ \\ $v_{n-1}$ & $0$ & $0$ & $\dots$ & $0$ & $0$ & $v_{n-1}$ & $0$ & $\dots$ & $a_{n/2} v_{n-1}$ & $\dots$ \\ $v_n$ & $0$ & $0$ & $\dots$ & $0$ & $0$ & $-v_n$ & $0$ & $\dots$ & $a_{n/2} v_n$ & $\dots$ \\ \end{tabular}\right)$$

где-то для простоты я некоторые вектора не донормировал, но суммарно $n/2$ первых векторов содержат по 2 ненулевых элемента, далее следующие $n/2$ уже по 4 ненулевых и т.д. и всего получается примерно $n \log_2 n$ ненулевых элементов получается.

А вот можно еще меньше для общего случая?

[zgemm]

ой, перед $v_4$ в третьем столбце и четвертой строке минус должен быть, а исправить уже нельзя...

[svv]

Ну, и $Q^TQ=E$, а не $0$.

[zgemm]

svv в сообщении #1636715 писал(а):

Ну, и $Q^TQ=E$, а не $0$.

да-да-да!!!

Но даже с учетом этого - все равно нет ни какого обсуждения. Не ужели эта тема тут ни кому не интересна? А представляете сколько там много обобщений на всякие LU разложения и аналогичные вещи?

[dgwuqtj]

Это выглядит как задача из области символьных вычислений. Вы привели по сути жадный алгоритм (когда каждый следующий столбец имеет наименьшее возможное количество ненулевых элементов). Я в этой области не разбираюсь и не могу сказать, возможно ли дальнейшее улучшение, известно ли оно, и тянет ли на полноценную научную статью. Сходу ничего не придумывается.

[zgemm]

dgwuqtj в сообщении #1636747 писал(а):

Это выглядит как задача из области символьных вычислений.

Спасибо большое за ответ! Да, примерно оттуда, я правда сам далеко не из той области, но там так интересно!

Для 4х мерного пространства в общем виде можно доказать, что больше 4х нулей сделать не получится. А вот можно ли получить меньше (4+3*4)*2=32 нуля например для 8ми мерного пространства - я, к сожалению доказать не могу, но, предполагаю, что такая тема кого-то может заинтересовать и он тоже скажет что-то.

[dgwuqtj]

Я нашёл статью G.-S. Cheon, B. L. Shader, Sparse orthogonal matrices and the Haar wavelet. Похоже, там доказывается оценка снизу в $(\lfloor \log_2 n \rfloor + 3) n - 2^{\lfloor \log_2 n \rfloor + 1}$ ненулевых элементов (точнее, это оценка для любой ортогональной матрицы, у которой есть столбец без нулей). То есть асимптотически это всё равно $n \log_2 n$. Вообще эти авторы такими вопросами много занимались.

Только LU-разложение тут вроде как ни при чём, произвольную матрицу нельзя как-то по хитрому разложить так, чтобы в разложении были ещё где-нибудь нули из соображений размерности.

[Rusurano]

dgwuqtj
Схожая оценка даётся в статье Gi-Sang Cheon, Bryan L. Shader, Sparsity of orthogonal matrices with restrictions. Полагаю, автора может это заинтересовать, поскольку рассматривается и случай неквадратной матрицы.

[zgemm]

dgwuqtj и Rusurano, огромное спасибо!!!

Да, точно, там много интересного! Я слышал от кого-то в начале 2000 про такие работы, но совсем вылетело из головы кто да как, вот и поднял эту тему.

Про LU - я имел ввиду как разреженной (это один класс, довольно интересных задач), так и разложение матриц на факторы, которые легко обращать, но которые имеют разреженность.

В разреженном - там да, много своей теории, как переставить матрицу так, чтобы само разложение не вызывало бы много новых ненулевых элементов. Даже когда-то такое программировал, но не могу похвастать, что где-то после этого смог эти результаты опубликовать или мои результаты встроились в какой-то известный программный пакет.

А вот просто разложения матриц - помню, что встречался, но подзабыл как это делается. Надеюсь, что после чтения ссылок и этих же авторов, что-то да вспомнится.