On sparse approximations of solutions to linear systems with orthogonal matrices

Full Text

1. Предварительные сведения

В настоящее время активно разрабатывается новый метод сжатия информации, основанный на снижении размерности данных. Простейшая модель такого сжатия выглядит так.

Рассмотрим линейную систему уравнений с прямоугольной матрицей [1$–$3]

                                                       $D_{n\times k}\alpha \mathrm{<mo>=</mo>}x\mathrm{,}k\ge n\mathrm{.}$

Например, для k=3, n=2 система принимает вид:

                                  $\left(\begin{array}{ccc}{d}_{11}& d_{12}& d_{13}\\ d_{21}& d_{22}& d_{23}\end{array}\right)\left(\begin{array}{ccc}{\alpha }_1& & \\ {\alpha }_2& & \\ {\alpha }_3& & \end{array}\right)\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}{x}_1& & \\ x_2& & \end{array}\right)\mathrm{.}$

Исходная информация моделируется вектором $\alpha \mathrm{,}$ сжатая $—$ вектором $x$ меньшей размерности. Матрицу $D$ принято называть словарем, а её столбцы $—$ атомами.

Предполагая, что ранг матрицы $D$ полный, система имеет бесконечное число решений. Для создания быстрых алгоритмов восстановления информации предпочтение отдается векторам, имеющим наибольшее количество нулевых координат. Такие решения называются разреженными. Тематика, связанная с разреженными представлениями, широко освещена в литературе, включая источники [1$–$10]. В общем виде можно сформулировать следующую задачу: найти такой функционал $Q\mathrm{,}$ минимизируя который можно было бы добиться единственности в выборе решения. Формально постановка задачи выглядит следующим образом: $\widehat{\alpha }\mathrm{<mo>=</mo>}arg\underset{\alpha }{{\displaystyle \min }}Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>}$ и $D\alpha \mathrm{<mo>=</mo>}x\mathrm{.}$ Традиционный выбор в качестве функционала $Q$ евклидовой нормы позволяет найти единственное решение, которое, однако, не является разреженным [1]. Для поиска разреженных решений интересно рассмотреть нормы и псевдонормы, отличные от евклидовой.

В данной работе будут рассмотрены функционалы вида $Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\left\{\begin{array}{l}\parallel \alpha {\parallel }_p^{p}p\mathrm{<mo>=</mo>1,2}\hfill \\ \parallel \alpha {\parallel }_{0}p\mathrm{<mo>=</mo>0}\hfill \end{array}\right.$.

Для $p\mathrm{<mo>=</mo>0}$ функционал $Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>}$ определяет количество ненулевых координат вектора $\alpha \mathrm{.}$

Для этого функционала формулируется задача минимизации $\mathrm{<mo\; stretchy="false">(</mo>}{P}_0\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo>}$ $\widehat{\alpha }\mathrm{<mo>=</mo>}arg\underset{\alpha }{{\displaystyle \min }}\parallel \alpha {\parallel }_0$ такая, что $D\alpha \mathrm{<mo>=</mo>}x$.

Представляет интерес и такая постановка задачи. Допускается $\epsilon$ -отклонение от точного решения системы, но по-прежнему сохраняется требование получить разреженное решение [4]. Одна из возможных постановок такой задачи выглядит так: $\mathrm{<mo\; stretchy="false">(</mo>}{P}_p^{\epsilon }\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo>}\widehat{\alpha }\mathrm{<mo>=</mo>}arg\underset{\alpha }{{\displaystyle \min }}Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>,}p\mathrm{<mo>=</mo>0,1,2}$ такое, что $\parallel D\alpha -x{\parallel }_2\le \epsilon \mathrm{.}$

 

2. Основные результаты

 В данной работе в качестве словаря рассматривается вещественная ортогональная $k\times k$ -матрица $D\mathrm{,}$ и для такого словаря решаются задачи $\mathrm{<mo\; stretchy="false">(</mo>}{P}_p^{\epsilon }\mathrm{<mo\; stretchy="false">)</mo>,}$ $p\mathrm{<mo>=</mo>0,}\mathrm{1,}2.$ Для решения поставленных задач составляется целевая функция [1] с параметром $\lambda \mathrm{<mo>></mo>0,}$ с классическими нормами при $p\mathrm{<mo>=</mo>1,}$ $p\mathrm{<mo>=</mo>2}$ и с псевдонормой при $p\mathrm{<mo>=</mo>0<mo>:</mo>}$ 

                                            $f\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}\parallel D\alpha -x{\parallel }_2^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>,}$

и задача сводится к нахождению вектора $\alpha \mathrm{,}$ который минимизирует определенную таким образом функцию, $\alpha \mathrm{,}x\in {ℝ}^k\mathrm{,}k\in \mathbb{N}\mathrm{.}\lambda \mathrm{<mo>></mo>0.}$

Используя ортогональность матрицы $D\mathrm{,}$ имеем:

                    $f\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}\parallel D\alpha -x{\parallel }_2^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}\parallel D\alpha -D{D}^{T}x{\parallel }_2^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}$

 

                           $\mathrm{<mo>=</mo>}\frac{1}{2}\parallel D\mathrm{<mo\; stretchy="false">(</mo>}\alpha -\beta \mathrm{<mo\; stretchy="false">)</mo>}{\parallel }_2^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}\parallel \mathrm{<mo\; stretchy="false">(</mo>}\alpha -\beta \mathrm{<mo\; stretchy="false">)</mo>}{\parallel }_2^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>.}$

В первом переходе использовалось свойство унитарности, $D{D}^T\mathrm{<mo>=</mo>}I$ . Второй осуществляется с использованием точного решения $\beta \mathrm{<mo>:</mo><mo>=</mo>}{D}^{T}x$. Последний переход использует изометрию унитарного преобразования относительно евклидовой нормы.

Получившееся равенство можно записать следующим образом:

                                         $f\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>1}}^k}\mathrm{<mo\; stretchy="false">[</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda Q\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">]</mo>.}$

Такая форма записи позволяет заменить задачу векторной оптимизации серией задач скалярной оптимизации.

 

3. Задача $\mathrm{<mo\; stretchy="false">(</mo>}{P}_0^{\epsilon }\mathrm{<mo\; stretchy="false">)</mo>}$ 

 

В этой задаче оптимальные координаты принимают вид:

                                           ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}arg\underset{{\alpha }_j}{{\displaystyle \min }}\mathrm{<mo\; stretchy="false">[</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda \mathrm{<mo\; stretchy="false">]</mo>}$

при ${\alpha }_j\ne 0$ и

                                                    ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}arg\underset{{\alpha }_j}{{\displaystyle \min }}\mathrm{<mo\; stretchy="false">[</mo>}\frac{1}{2}{\beta }_j^2\mathrm{<mo\; stretchy="false">]</mo>}$

при ${\alpha }_j\mathrm{<mo>=</mo>0.}$

Минимум первой функции достигается при ${\alpha }_j\mathrm{<mo>=</mo>}{\beta }_j$ и равен $\lambda \mathrm{<mo>;</mo>}$ а минимум второй достигается при ${\alpha }_j\mathrm{<mo>=</mo>0}$ и равен ${\beta }_j^2\mathrm{<mo>/</mo>2.}$

Сравним найденные экстремумы для получения условий для ${\alpha }_j^{opt}$ 

                                                  $\frac{1}{2}{\beta }_j^2\le \lambda \mathrm{,}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \sqrt{2\lambda }\mathrm{.}$

Соответственно

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left\{\begin{array}{l}\mathrm{0<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \sqrt{2\lambda }\mathrm{,}\hfill \\ {\beta }_j\mathrm{<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo><mo>></mo>}\sqrt{2\lambda }\mathrm{.}\hfill \end{array}\right.$ 

 

 

Рис. 1. График зависимости оптимальных координат от параметра λ для ℓ0 квазинормы

Fig. 1. Graph of the dependence of the optimal coordinates αj on the parameter λ for the ℓ0 quasi-norm

 

  Данный график (рис. 1) известен как жесткий порог. Для $\mathrm{<mo>|</mo>}\beta \mathrm{<mo>|</mo>}\le \sqrt{2\lambda }$ оптимальным представлением будет $\alpha \mathrm{<mo>=</mo>0}$. Когда $\mathrm{<mo>|</mo>}\beta \mathrm{<mo>|</mo>}\ge \sqrt{2\lambda }$, оптимальное представление $\alpha \mathrm{<mo>=</mo>}\beta$. Таким образом, варьируя невязку и параметр $\lambda$, можно сделать нулевыми те координаты точного решения $\beta$, которые удовлетворяют условию $\mathrm{<mo>|</mo>}\beta \mathrm{<mo>|</mo>}\le \sqrt{2\lambda }$.

 

4. Задача $\mathrm{<mo\; stretchy="false">(</mo>}{P}_1^{\epsilon }\mathrm{<mo\; stretchy="false">)</mo>}$ 

 При рассмотрении нормы ${\mathcal{l}}_1$ функции $Q\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo>|</mo>}{\alpha }_j\mathrm{<mo>|</mo>}$, используя целевую функцию $\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda Q$, можно получить оптимизационную задачу [4]

                                       ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}arg\underset{{\alpha }_j}{{\displaystyle \min }}\mathrm{<mo\; stretchy="false">[</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda \mathrm{<mo>|</mo>}{\alpha }_j\mathrm{<mo>|</mo><mo\; stretchy="false">]</mo>.}$

Находим значение ${\alpha }_j$, при котором $F\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda \mathrm{<mo>|</mo>}{\alpha }_j\mathrm{<mo>|</mo>}$ достигает минимума.

Для этого найдем критические точки, в которых $F^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$ или $F^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo>}$ не существует. Производная представлена следующим выражением:

                                        $F^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\alpha }_j-{\beta }_j+\lambda \frac{{\alpha }_j}{\mathrm{<mo>|</mo>}{\alpha }_j\mathrm{<mo>|</mo>}}\mathrm{,}{\alpha }_j\ne 0.$

$F^{\prime }$ разбивается на два случая

 $F^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\left\{\begin{array}{l}{\alpha }_j-{\beta }_j+\lambda {\alpha }_j\mathrm{<mo>></mo>0,}\hfill \\ {\alpha }_j-{\beta }_j-\lambda {\alpha }_j\mathrm{<mo><</mo>0.}\hfill \end{array}\right.$ 

 

Рассмотрим случай ${\alpha }_j\mathrm{<mo>></mo>0}$ 

                                              ${F^{\prime }}_1\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\alpha }_j-{\beta }_j+\lambda \mathrm{<mo>;</mo>}{\alpha }_j\mathrm{<mo>></mo>0.}$

Приравниваем к нулю, получаем одну критическую точку

                                                           ${\alpha }_j\mathrm{<mo>=</mo>}{\beta }_j-\lambda \mathrm{.}$

 Проделаем то же самое с ${F^{\prime }}_2\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\alpha }_j-{\beta }_j-\lambda \mathrm{<mo>;</mo>}{\alpha }_j\mathrm{<mo><</mo>0.}$ Приравниваем к нулю, получаем одну критическую точку

                                                           ${\alpha }_j\mathrm{<mo>=</mo>}{\beta }_j+\lambda \mathrm{.}$

Для доказательства того, что данные критические точки является точками минимума, необходимо взять вторую производную и проверить найденные критические точки. ${F^{\prime }}^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1}\Rightarrow {\beta }_j+\lambda$ и ${\beta }_j-\lambda$ $—$ минимумы функции.

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

${\beta }_j-\lambda \mathrm{<mo><</mo>0}\Rightarrow {\beta }_j\mathrm{<mo><</mo>}\lambda \mathrm{,}$ 

${\beta }_j+\lambda \mathrm{<mo><</mo>0}\Rightarrow {\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{.}$

Проверяем оставшуюся критическую точку

 $\left\{\begin{array}{l}\mathrm{0<mo><</mo>}{\beta }_j+\lambda \mathrm{<mo>;</mo>}\hfill \\ \mathrm{0<mo><</mo>}{\beta }_j-\lambda \mathrm{<mo>;</mo>}\hfill \end{array}\right.\Rightarrow \left\{\begin{array}{l}{\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{<mo>;</mo>}\hfill \\ {\beta }_j\mathrm{<mo><</mo>}\lambda \mathrm{.}\hfill \end{array}\right.$ 

 

При сравнении ${\beta }_j+\lambda$ и ${\beta }_j-\lambda$ получаем, что $-\lambda \mathrm{<mo><</mo>}\lambda$ или $-\lambda \mathrm{<mo>></mo>}\lambda$. Так как $\lambda \mathrm{<mo>></mo>0}$, можно прийти к выводу, что ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}{\beta }_j-\lambda$ используется при ${\beta }_j\mathrm{<mo>></mo>}\lambda \mathrm{<mo>></mo>0}$, а ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}{\beta }_j+\lambda$ при ${\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{<mo><</mo>0}$.

Таким образом, решение задачи минимизации для ${\mathcal{l}}_1$ нормы можно записать в таком виде:

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left\{\begin{array}{l}{\beta }_j-\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo>></mo>}\lambda \mathrm{,}\hfill \\ \mathrm{0<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \lambda \mathrm{,}\hfill \\ {\beta }_j+\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{.}\hfill \end{array}\right.$ 

 

 

Рис. 2. График зависимости оптимальных координат αj от параметра λ для ℓ1 нормы

Fig. 2. Graph of the dependence of the optimal coordinates αj on the parameter λ for the ℓ1 norm 

 

Таким образом, варьируя невязку и параметр $\lambda$, получаем возможность сделать нулевыми те координаты точного решения $\beta$, которые удовлетворяют условию $\mathrm{<mo>|</mo>}\beta \mathrm{<mo>|</mo>}\le \lambda$ (рис. 2).

 

5. Задача $\mathrm{<mo\; stretchy="false">(</mo>}{P}_2^{\epsilon }\mathrm{<mo\; stretchy="false">)</mo>}$ 

 При рассмотрении нормы ${\mathcal{l}}_2$ функции Q, получаем $Q\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo>|</mo>}{\alpha }_j{\mathrm{<mo>|</mo>}}^2\mathrm{.}$

Таким образом, оптимизационная задача сводится к следующему виду:

                                      ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}arg\underset{{\alpha }_j}{{\displaystyle \min }}\mathrm{<mo\; stretchy="false">[</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda \mathrm{<mo>|</mo>}{\alpha }_j{\mathrm{<mo>|</mo>}}^2\mathrm{<mo\; stretchy="false">]</mo>,}$

$F\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda \mathrm{<mo>|</mo>}{\alpha }_j{\mathrm{<mo>|</mo>}}^2\mathrm{,}$ $F\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}{\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j-{\beta }_j\mathrm{<mo\; stretchy="false">)</mo>}}^2+\lambda {\alpha }_j^2\mathrm{.}$ Находим значение ${\alpha }_j$, при котором $F\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo>}$ достигает минимума.

                                                 $F^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}{\alpha }_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\alpha }_j-{\beta }_j+2\lambda {\alpha }_j\mathrm{.}$

Приравниваем к нулю, получаем одну критическую точку

                                                           ${\alpha }_j\mathrm{<mo>=</mo>}\frac{{\beta }_j}{1+2\lambda }\mathrm{.}$

Данная точка является точкой минимума функции. Следовательно, ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\frac{{\beta }_j}{1+2\lambda }$.

 

Рис. 3. График зависимости оптимальных координат αj от параметра λ для ℓ2 нормы

Fig. 3. Graph of the dependence of the optimal coordinates αj on the parameter λ for the ℓ2 norm

 

Таким образом, получаем, что ${\mathcal{l}}_2$ норма не позволяет получить дополнительных нулевых координат (рис. 3).

 

6. Примеры нахождения разреженных решений

 В качестве словаря возьмем единичную матрицу $4\times 4$ 

 $D\mathrm{<mo>=</mo>}{D}^T\mathrm{<mo>=</mo>}\left(\begin{array}{l}1000\hfill \\ 0100\hfill \\ 0010\hfill \\ 0001\hfill \end{array}\right)$ 

 

 

 $\overrightarrow{x}\mathrm{<mo>=</mo>}\left(\begin{array}{l}11\hfill \\ 6\hfill \\ 3\hfill \\ 2\hfill \end{array}\right)$ 

 

 

 $\overrightarrow{\beta }\mathrm{<mo>=</mo>}\left(\begin{array}{l}11\hfill \\ 6\hfill \\ 3\hfill \\ 2\hfill \end{array}\right)$ 

 

Возьмем $\lambda \mathrm{<mo>=</mo>2}$. Для ${\mathcal{l}}_1$ нормы оптимальным решением будет:

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left\{\begin{array}{l}{\beta }_j-\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo>></mo>}\lambda \mathrm{,}\hfill \\ \mathrm{0<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \lambda \mathrm{,}\hfill \\ {\beta }_j+\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{,}\hfill \end{array}\right.$ 

 

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left(\begin{array}{l}9\hfill \\ 4\hfill \\ 1\hfill \\ 0\hfill \end{array}\right)\mathrm{.}$ 

 

Таким образом, мы получили более разреженное решение для вектора $x\mathrm{.}$ Нетрудно заметить, что при использовании ${\mathcal{l}}_1$ нормы всегда можно получить более разреженное решение путем соответствующего выбора $\lambda$.

Также можно заметить, что при использовании ${\mathcal{l}}_2$ нормы и ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\frac{{\beta }_j}{1+2\lambda }$ невозможно получить ${\alpha }_j$, отличное от 0 при ${\beta }_j\ne 0$. Таким образом, норма ${\mathcal{l}}_2$ не может решить поставленную задачу.

Используя псевдонорму ${\mathcal{l}}_0\mathrm{,}$ имеем

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left\{\begin{array}{l}\mathrm{0<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \sqrt{2\lambda }\mathrm{,}\hfill \\ {\beta }_j\mathrm{<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo><mo>></mo>}\sqrt{2\lambda }\hfill \end{array}\right.$ 

 и, изменяя параметр $\lambda \mathrm{,}$ можно получить любое количество нулевых координат приближенного решения.

В качестве словаря возьмем ортогональную матрицу $4\times 4$

 

 $D\mathrm{<mo>=</mo>}{D}^T\mathrm{<mo>=</mo>}\frac{1}{2}\left(\begin{array}{l}1111\hfill \\ 1-11-1\hfill \\ 11-1-1\hfill \\ 1-1-11\hfill \end{array}\right)$ 

 

 

 $\overrightarrow{x}\mathrm{<mo>=</mo>}\left(\begin{array}{l}11\hfill \\ 6\hfill \\ 3\hfill \\ 2\hfill \end{array}\right)$ 

 

 

 $\overrightarrow{\beta }\mathrm{<mo>=</mo>}\left(\begin{array}{l}11\hfill \\ 3\hfill \\ 6\hfill \\ 2\hfill \end{array}\right)$ 

 

Возьмем $\lambda \mathrm{<mo>=</mo>2}$. Для ${\mathcal{l}}_1$ нормы оптимальным решением будет:

 

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left\{\begin{array}{l}{\beta }_j-\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo>></mo>}\lambda \mathrm{,}\hfill \\ \mathrm{0<mo>;</mo>}\mathrm{<mo>|</mo>}{\beta }_j\mathrm{<mo>|</mo>}\le \lambda \mathrm{,}\hfill \\ {\beta }_j+\lambda \mathrm{<mo>;</mo>}{\beta }_j\mathrm{<mo><</mo>}-\lambda \mathrm{,}\hfill \end{array}\right.$ 

 

 

 ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\left(\begin{array}{l}9\hfill \\ 1\hfill \\ 4\hfill \\ 0\hfill \end{array}\right)$ 

 

Таким образом, мы получили одну дополнительную нулевую координату.

 

Выводы

 Выбор параметра $\lambda$ позволяет регулировать количество нулевых координат в зависимости от выбранной невязки $\epsilon$. При использовании ${\mathcal{l}}_0$ или ${\mathcal{l}}_1$ нормы всегда можно получить более разреженное решение путем соответствующего выбора $\lambda$.

Также можно заметить, что при использовании ${\mathcal{l}}_2$ нормы и ${\alpha }_j^{opt}\mathrm{<mo>=</mo>}\frac{{\beta }_j}{1+2\lambda }$ невозможно получить ${\alpha }_j\mathrm{,}$ отличное от 0, при ${\beta }_j\ne 0$. Таким образом, ${\mathcal{l}}_2$ норма не позволяет получить дополнительных нулевых координат в приближенном представлении точного решения.

 

About the authors

Andrei V. Kiptenko

Samara National Research University

Author for correspondence.
Email: kiptenkoandrei@yandex.ru
ORCID iD: 0009-0001-3837-1013

post-graduate student of the Department of Information Security

Russian Federation, 34, Moskovskoye shosse, Samara, 443086

Ilia M. Izbiakov

Samara National Research University

Email: iliya-izbyakov@mail.ru
ORCID iD: 0000-0003-3358-966X

post-graduate student of the Department of Information Security

Russian Federation, 34, Moskovskoye shosse, Samara, 443086

References

Supplementary files