Восполнение матриц с дополнительной информацией - История изменений

Михайлов Арсений: /* Литература */

2021-10-26T20:36:54Z

Литература

← Предыдущая версия		Версия от 20:36, 26 октября 2021
Строка 90:		Строка 90:
	[1] Guaranteed Rank Minimization via Singular Value Projection.Raghu Meka, Prateek Jain, Inderjit S. Dhillon // arXiv:0909.5457		[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~~		[2] Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. M Xu, R Jin, ZH Zhou

	[[en:Matrix completion]]		[[en:Matrix completion]]

	[[Категория:~~Восстановление~~ матриц]]		[[Категория:Восполнение матриц]]

Михайлов Арсений: /* Общее описание алгоритма */

2021-10-26T20:32:19Z

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

← Предыдущая версия		Версия от 20:32, 26 октября 2021
Строка 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>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</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>.		Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T20:30:38Z

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

← Предыдущая версия		Версия от 20:30, 26 октября 2021
Строка 17:		Строка 17:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>~~. Зададим ортонормированные матрицы~~ <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> ~~базисы~~ этих пространств, соответственно. ~~Тогда~~ <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для ~~матрицы <math>Z</math>, а именно~~:		Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>, тогда <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> ортонормированные матрицы базисов этих пространств, соответственно. Для матрицы <math>X</math> существует представление: <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

	<table style="width:100%">		<table style="width:100%">
Строка 26:		Строка 26:
	<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.		<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

	Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал ~~будет~~ с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.		Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будем с помощью алгоритма SVP с оператором <math>\mathcal{A}(Z) = \mathcal{P}_\Omega(AZB^T)</math>.
	<table style="width:100%">		<table style="width:100%">
	<tr>		<tr>

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T20:23:33Z

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

← Предыдущая версия		Версия от 20:23, 26 октября 2021
Строка 33:		Строка 33:
	</table>		</table>
	где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).		где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).
	Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
			Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
	<table style="width:100%">		<table style="width:100%">
	<tr>		<tr>
	<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(~~AZB~~^T - X)B, </math></td>		<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] </math></td>
	</tr>		</tr>
	</table>		</table>

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T20:21:20Z

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

← Предыдущая версия		Версия от 20:21, 26 октября 2021
Строка 32:		Строка 32:
	</tr>		</tr>
	</table>		</table>
	Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, ~~\cP_~~{\Omega}(X)B </math> получим алгоритм:		где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).
			Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
	<table style="width:100%">		<table style="width:100%">
	<tr>		<tr>

Михайлов Арсений: /* Свойства и структура алгоритма */

2021-10-26T20:16:56Z

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

← Предыдущая версия		Версия от 20:16, 26 октября 2021
Строка 30:		Строка 30:
	<tr>		<tr>
	<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>		<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
			</tr>
			</table>
			Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \cP_{\Omega}(X)B </math> получим алгоритм:
			<table style="width:100%">
			<tr>
			<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZB^T - X)B, </math></td>
	</tr>		</tr>
	</table>		</table>

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T20:11:56Z

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

← Предыдущая версия		Версия от 20:11, 26 октября 2021
Строка 24:		Строка 24:
	</tr>		</tr>
	</table>		</table>
	<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega} = ~~\mathds{~~1}[(i, j) \in \Omega] \circ X</math> - проектор на это множество.		<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

	~~Эта задача эквивалента~~ задачи ~~восполнения~~ <math>X</math>~~, если~~ <math>X</math> ~~единственная матрица ранга не выше~~ <math>r</math>~~, для которой~~ \mathcal{P}_{\~~Omega~~}(X) ~~совпадает с известными нам элементами~~, ~~и для которой столбцы и строки лежат в~~ <math>~~L_A~~</~~math~~> и <~~math~~>~~L_B~~</~~math~~>~~. Это верно не всегда (что приводит к расходимости алгоритма), но при о~~		Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будет с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.
			<table style="width:100%">
			<tr>
			<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
			</tr>
			</table>

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

Михайлов Арсений: /* Свойства и структура алгоритма */

2021-10-26T20:02:49Z

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

← Предыдущая версия		Версия от 20:02, 26 октября 2021
Строка 19:		Строка 19:
	Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:		Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

	<tr>		<table style="width:100%">
	<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} \|\|\mathcal{P}_{\Omega}(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r\</math></td>		<tr>
	</tr>		<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} \|\|\mathcal{P}_{\Omega}(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
			</tr>
			</table>
			<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega} = \mathds{1}[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

			Эта задача эквивалента задачи восполнения <math>X</math>, если <math>X</math> единственная матрица ранга не выше <math>r</math>, для которой \mathcal{P}_{\Omega}(X) совпадает с известными нам элементами, и для которой столбцы и строки лежат в <math>L_A</math> и <math>L_B</math>. Это верно не всегда (что приводит к расходимости алгоритма), но при о

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

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T19:45:25Z

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

← Предыдущая версия		Версия от 19:45, 26 октября 2021
Строка 19:		Строка 19:
	Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:		Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

			<tr>
	<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} \|\|\mathcal{P}_{\Omega}(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r\</math></td>		<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} \|\|\mathcal{P}_{\Omega}(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r\</math></td>
			</tr>

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

Михайлов Арсений: /* Математическое описание алгоритма */

2021-10-26T19:43:56Z

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

← Предыдущая версия		Версия от 19:43, 26 октября 2021
Строка 19:		Строка 19:
	Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:		Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

	~~\[\label{pr:Z}~~		<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} \|\|\mathcal{P}_{\Omega}(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r\</math></td>
	\min_{Z} f(Z) = \frac{1}{2} \|\|\~~cPo~~(AZB^T - X)\|\|^2_2, \; \; rank(Z) \leq r\
	\]



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