Вычислить SVD эскиза матрицы низкого ранга
[ возвращает разложение сингулярного значения (SVD) эскиза матрицы низкого ранга входной матрицы U,S,V] = svdsketch(A)A. Эскиз матрицы представляет собой аппроксимацию низкого ранга, которая отражает только наиболее важные особенности A (до допуска), что позволяет быстрее вычислять частичный SVD больших матриц по сравнению с использованием svds.
[ дополнительно возвращает вектор U,S,V,apxErr] = svdsketch(___)apxErr который содержит относительную аппроксимационную ошибку в каждой итерации, norm(U*S*V'-A,'fro')/norm(A,'fro'). Заключительная запись в векторе apxErr(end) - относительная аппроксимационная ошибка выходного сигнала, возвращаемого svdsketch.
Использовать svdsketch для вычисления коэффициентов SVD аппроксимации матрицы низкого ранга.
Использовать gallery для создания случайной матрицы 200 на 200 с геометрически распределенными сингулярными значениями.
A = gallery('randsvd',200);Использовать svdsketch для вычисления SVD низкоранговой аппроксимации A.
[U,S,V] = svdsketch(A);
Проверьте размер выходов.
size(S)
ans = 1×2
120 120
Результаты показывают, что матричное приближение низкого ранга A имеет звание 120.
Задание допуска с помощью svdsketch для вычисления коэффициентов SVD аппроксимации матрицы низкого ранга. svdsketch адаптивно определяет соответствующий ранг эскиза матрицы на основе заданного допуска.
Использовать gallery для создания случайной матрицы 200 на 200 с геометрически распределенными сингулярными значениями.
A = gallery('randsvd',200);Использовать svdsketch для расчета SVD низкоранговой аппроксимации A. Укажите допуск 1e-2и найти размер вывода S для определения ранга svdsketch использует для эскиза матрицы.
tol = 1e-2; [U,S,V] = svdsketch(A,tol); size(S)
ans = 1×2
60 60
Результаты показывают, что матричное приближение низкого ранга A имеет звание 60.
Анализ аппроксимации эскиза матрицы A сравнивая A кому U*S*V'.
norm(U*S*V' - A,'fro')/norm(A,'fro')
ans = 0.0048
Результат показывает, что эскиз матрицы аппроксимирован A в пределах указанного допуска 1e-2.
Использовать svdsketch с MaxSubspaceDimension на матрице, которая имеет медленно затухающие сингулярные значения. Этот параметр можно использовать для принудительного использования svdsketch для использования подмножества функций A в эскизе матрицы.
Создайте матрицу 5000 на 5000 со значениями, полученными из стандартного нормального распределения. Просмотр распределения сингулярных значений матрицы.
A = randn(5000);
semilogy(svd(A),'-o')
Поскольку сингулярные значения в A медленно распадаются, A имеет много важных особенностей и не поддается низкоранговым приближениям. Чтобы сформировать эскиз матрицы, который разумно аппроксимирует A, большинство или почти все элементы должны быть сохранены.
Использовать svdsketch на матрице с допуском 1e-5. Укажите четыре выхода, чтобы вернуть коэффициенты SVD, а также относительную ошибку аппроксимации в каждой итерации.
tol = 1e-5; [U1,S1,V1,apxError1] = svdsketch(A,tol); size(S1)
ans = 1×2
5000 5000
Размер S указывает, что для удовлетворения допуска, svdsketch необходимо сохранить все особенности A. Для больших разреженных входных матриц это может представлять проблемы с памятью, поскольку аппроксимация низкого ранга A образованные svdsketch приблизительно тот же размер, что и A и, таким образом, может не поместиться в памяти в виде плотной матрицы.
Проверьте погрешность аппроксимации выходов. С тех пор svdsketch сохраняет все в A, вычисленный ответ является точным, но вычисление было просто дорогостоящим способом вычисления svd(X).
apxError1(end)
ans = 1.9075e-08
Теперь выполните тот же расчет, но укажите MaxSubspaceDimension 650 для ограничения размера подпространства, используемого для построения эскиза A. Это полезно, чтобы заставить svdsketch для использования только подмножества элементов в A для формирования эскиза матрицы, уменьшая размер выходных данных.
[U2,S2,V2,apxError2] = svdsketch(A,tol,'MaxSubspaceDimension',650);
size(S2)ans = 1×2
650 650
Теперь выходные данные имеют меньший размер.
Проверьте погрешность аппроксимации новых выходов. Компромисс для того, чтобы заставить выходные сигналы быть меньше, заключается в том, что многие важные признаки А должны быть опущены в эскизе матрицы, и результирующее приближение ранга 650 A не соответствует указанному допуску.
apxError2(end)
ans = 0.8214
Использовать svdsketch когда вы не знаете заранее, какой ранг указать svds, но вы знаете, какой допуск должно удовлетворять приближение SVD.
svds вычисляет наилучшую возможную аппроксимацию ранга-k SVD (используя значение по умолчанию "largest" метод). svdsketch не гарантирует, что его ранг-k аппроксимация является лучшим, что объясняет его скорость преимущество перед svds.
svdsketch применяет допуск для формирования аппроксимации матрицы низкого ранга входной матрицы A. Эта аппроксимация низкого ранга называется матрицей. Эскиз матрицы сохраняет только важные элементы из Aфильтрация ненужной информации. Ошибка относительного приближения apxErr эскиз матрицы предназначен для удовлетворения заданного допуска tol:
Процесс svdsketch для формирования эскиза матрицы:
svdsketch формирует эскиз матрицы итеративно, при этом каждая итерация добавляет новые столбцы к Q и новые строки к B. Новые столбцы и строки создаются путем извлечения элементов из A используя матрицу случайной выборки. Можно управлять количеством столбцов и строк, добавленных в каждую итерацию, с помощью BlockSize пара имя-значение.
Во время каждой итерации svdsketch использует итерации мощности для улучшения ортогональности новых столбцов в Q. Можно настроить количество итераций мощности с помощью NumPowerIterations пара имя-значение.
Итерации для формирования эскиза матрицы останавливаются, когда количество столбцов в Q и строк в B достигает указанного значения для MaxSubspaceDimension, число итераций достигает MaxIterationsили сходится относительная аппроксимационная ошибка (apxErr <= tol).
Для повышения скорости сходимости svdsketch может увеличить указанное начальное значение для BlockSize от итерации к итерации, если затухание в apxErr недостаточно.
После формирования эскиза матрицы svdsketch вычисляет разложение сингулярного значения (SVD) эскиза матрицы с помощью [U1,S,V] = svd(B,'econ'), такой, что
USVH.
Если svdsketch способен отфильтровывать некоторые функции A на основе указанного допуска, тогда результирующие SVD-факторы содержат меньше сингулярных значений и сингулярных векторов, чем если бы полный SVD был выполнен на A.
[1] Юй, Вэньцзянь, Юй Гу и Яохан Ли. «Эффективные рандомизированные алгоритмы для аппроксимации матрицы низкого ранга с фиксированной точностью». Журнал SIAM по матричному анализу и приложениям 39, № 3 (август 2018): 1339-1359. https://doi.org/10.1137/17M1141977.