Вычисление SVD низкорангового матричного эскиза
[ возвращает сингулярное разложение (SVD) матричного эскиза низкого ранга входа матрицы U,S,V] = svdsketch(A)A. Матричный эскиз является низкоранговым приближением, которое отражает только наиболее важные функции A (до допуска), что позволяет быстрее вычислять частичный SVD больших матриц по сравнению с использованием svds.
Использование 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
Теперь выходные параметры имеют меньший размер.
Проверьте ошибку приближения новых выходов. Компромисс для принуждения выходов к меньшему заключается в том, что многие важные функции A должны быть опущены в матричном эскизе, и полученное приближение ранга 650 A не соответствует указанному допуску.
apxError2(end)
ans = 0.8214
Использовать svdsketch когда вы не знаете раньше времени, с каким рангом указывать svds, но вы знаете, какой допуск должно удовлетворять приближение SVD.
svds вычисляет лучшее возможное приближение SVD к рангу k (используя значение по умолчанию "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'), таким что
Если svdsketch способен отфильтровать некоторые функции A основываясь на заданном допуске, тогда результирующие коэффициенты SVD содержат меньше сингулярных значений и сингулярных векторов, чем если бы полный SVD был выполнен на A.
[1] Ю, Вэньцзянь, Юй Гу и Яохан Ли. Эффективные рандомизированные алгоритмы для низкоранговой Матрицы с фиксированной точностью Приближения. SIAM Journal по матричному анализу и применениям 39, № 3 (август 2018): 1339-1359. https://doi.org/10.1137/17M1141977.