Восполнение матриц с дополнительной информацией: различия между версиями

[непроверенная версия]

Версия 22:16, 26 октября 2021

Восстановление матриц
Последовательный алгоритм
Последовательная сложность	$O(n^3)$
Объём входных данных	[math]\frac{n (n + 1)}{2}[/math]
Объём выходных данных	[math]\frac{n (n + 1)}{2}[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(n)[/math]
Ширина ярусно-параллельной формы	[math]O(n^2)[/math]

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Пусть [math]X \in \mathbb{R}^{n_1 \times n_2} - [/math] неизвестная малоранговая матрица. Нашей целью является восполнение матрицы [math]X[/math], то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства [math]L_A[/math] и [math]L_B[/math], содержащие столбцы и строки матрицы [math]X[/math] соответственно. Если [math]L_A[/math] и [math]L_B[/math] тривиальные (то есть совпадают с [math]\mathbb{R}^{n_1}[/math] и [math]\mathbb{R}^{n_2}[/math]), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице [math]X[/math].

1.2 Математическое описание алгоритма

1.3 Макроструктура алгоритма

1.4 Схема реализации последовательного алгоритма

1.5 Последовательная сложность алгоритма

1.6 Информационный граф

1.7 Ресурс параллелизма алгоритма

1.8 Входные и выходные данные алгоритма

1.9 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

[1] Guaranteed Rank Minimization via Singular Value Projection.Raghu Meka, Prateek Jain, Inderjit S. Dhillon // arXiv:0909.5457

[2] Low-rank matrix completion by Riemannian optimization. Bart Vandereycken // arXiv:0909.5457

@@ Строка 12: / Строка 12: @@
 === Общее описание алгоритма ===
-Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math>, и <math>L_B \, - </math>, содержащие столбцы и строки матрицы <math>X</math> соответственно.
+Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.
+Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.
 === Математическое описание алгоритма ===