svdsketch

Вычислите SVD матричного эскиза низкого ранга

Описание

пример

[U,S,V] = svdsketch(A) возвращает сингулярное разложение (SVD) матричного эскиза низкого ранга входной матрицы A. Матричный эскиз является приближением низкого ранга, которое только отражает самые важные функции A (до допуска), который включает более быстрое вычисление частичного SVD больших матриц по сравнению с использованием svds.

пример

[U,S,V] = svdsketch(A,tol) задает допуск к матричному эскизу. svdsketch использование tol адаптивно определить ранг матричного приближения эскиза. Когда допуск становится больше, меньше функций A используются в матричном эскизе.

пример

[U,S,V] = svdsketch(A,tol,Name,Value) задает дополнительные опции с одним или несколькими Name,Value парные аргументы. Например, можно задать 'MaxIterations' и скаляр, чтобы настроить количество итераций раньше формировал матричный эскиз.

пример

[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')

Figure contains an axes. The axes contains an object of type line.

Начиная с сингулярных значений в 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

Входные параметры

свернуть все

Введите матрицу в виде разреженной или полной матрицы. A обычно, но не всегда, большая и разреженная матрица. svdsketch подходит лучше всего, чтобы работать с матрицами неполного ранга, которые имеют относительно небольшое количество функций.

Типы данных: single | double
Поддержка комплексного числа: Да

Матричный допуск эскиза в виде действительного числового скаляра в области значений sqrt(eps(class(A))) <= tol < 1.

svdsketch использует значение tol адаптивно определить который функции A использовать в приближении низкого ранга (матричный эскиз) A. Как значение tol увеличения, svdsketch использует меньше функций A сформировать матричный эскиз.

Пример: [U,S,V] = svdsketch(A,1e-4)

Типы данных: single | double

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: [U,S,V] = svdsketch(A,1e-10,'MaxIterations',100) использование 100 итераций в svdsketch алгоритм.

Максимальная размерность подпространства в виде положительного целочисленного скаляра. Размерность подпространства управляет потреблением памяти svdsketch алгоритм. Если алгоритм исчерпывает память для заданного допуска, то можно задать меньшее значение для MaxSubspaceDimension так, чтобы алгоритм остался в памяти. Например, корректировка этого параметра может быть полезной когда A имеет сингулярные значения то затухание медленно.

Когда вы задаете MaxSubspaceDimension опция, вы устанавливаете максимальное значение на ранге матричного эскиза, используемого svdsketch. Поэтому, если svdsketch не может удовлетворить заданному допуску рангом, меньшим, чем MaxSubspaceDimension, это использует максимальный позволенный ранг, и получившиеся выходные параметры не могут удовлетворить заданному допуску.

Пример: [U,S,V] = svdsketch(A,1e-7,'MaxSubspaceDimension',150)

Типы данных: single | double

Начальный размер блока алгоритма в виде положительного целочисленного скаляра. Размер блока является номером, на который ранг матричного эскиза увеличивает каждую итерацию. Больший размер блока сокращает количество необходимых итераций путем выполнения большего, работают на итерацию, но может также добавить больше информации в вычисление, чем необходимо, чтобы достигнуть сходимости.

Когда алгоритм продолжает, svdsketch может настроить размер блока от начального значения, чтобы ускорить сходимость если относительная ошибка приближения apxErr не затухает достаточно быстро.

Если вы задаете BlockSize, значение должно быть меньшим, чем MaxSubspaceDimension.

Пример: [U,S,V] = svdsketch(A,1e-7,'BlockSize',10)

Типы данных: single | double

Максимальное количество итераций алгоритма в виде положительного целочисленного скаляра. Больше итераций может произвести матричный эскиз более высокого качества за счет большего количества времени выполнения и более высокого потребления памяти.

Пример: [U,S,V] = svdsketch(A,1e-7,'MaxIterations',25)

Типы данных: single | double

Количество итераций степени в виде неотрицательного целочисленного скаляра. Итерации степени улучшают ортогональность U и V выходные параметры . Необходимо обычно выбирать количество итераций степени, чтобы быть 0, 1, или 2, когда большие значения могут неблагоприятно способствовать ошибке округления.

Пример: [U,S,V] = svdsketch(A,1e-7,'NumPowerIterations',2)

Типы данных: single | double

Выходные аргументы

свернуть все

Оставленные сингулярные векторы из матричного эскиза, возвращенного как матрица. Столбцы U ортонормированы, и они формируют набор базисных векторов для области значений матричного эскиза A.

Размер U зависит от значения tol. Как tol становится больше, svdsketch использует меньше функций входной матрицы, чтобы сформировать матричный эскиз, таким образом, U и V также имейте меньше столбцов.

Различные машины и релизы MATLAB® могут произвести различные сингулярные векторы, которые все еще численно точны. Соответствующие столбцы в U и V может инвертировать их знаки, поскольку это не влияет на значение выражения A = U*S*V'.

Сингулярные значения матричного эскиза, возвращенного как квадратная диагональная матрица. Диагональные элементы S строго положительные сингулярные значения матричного эскиза в порядке убывания.

Размер S зависит от значения tol. Когда допуск увеличивается, svdsketch использует меньше функций входной матрицы, чтобы сформировать матричный эскиз, таким образом, S имеет соответственно меньше строк и столбцов.

Правильные сингулярные векторы из матричного эскиза, возвращенного как матрица. Столбцы V ортонормированы, и они формируют набор базисных векторов для ядра матричного эскиза A.

Размер V зависит от значения tol. Как tol становится больше, svdsketch использует меньше функций входной матрицы, чтобы сформировать матричный эскиз, таким образом, U и V также имейте меньше столбцов.

Различные машины и релизы MATLAB могут произвести различные сингулярные векторы, которые все еще численно точны. Соответствующие столбцы в U и V может инвертировать их знаки, поскольку это не влияет на значение выражения A = U*S*V'.

Относительная ошибка приближения в каждой итерации, возвращенной как вектор. Длина apxErr равно количеству итераций, используемых в svdsketch алгоритм. Используйте MaxIterations настраивать количество итераций.

Записи apxErr относительные ошибки приближения в каждой итерации, norm(U*S*V'-A,'fro')/norm(A,'fro'). Итоговая запись в векторном apxErr(end) относительная ошибка приближения выходного параметра, возвращенного svdsketch.

Советы

  • Использование svdsketch когда вы не знаете заранее что ранг задать с svds, но вы знаете, какому допуску приближение SVD должно удовлетворить.

  • svds вычисляет самое лучшее приближение ранга-k SVD (использующий "largest" по умолчанию метод). svdsketch не гарантирует, что его приближение ранга-k является лучшим, которое составляет его преимущество скорости svds.

Алгоритмы

svdsketch применяет допуск, чтобы сформировать матричное приближение низкого ранга AQB из входной матрицы A. Это приближение низкого ранга называется матричным эскизом. Матричный эскиз только сохраняет важные функции от A, фильтрование ненужной информации. Относительная ошибка приближения apxErr из матричного эскиза стремится удовлетворять заданному допуску tol:

esketch=QBAFAFtol

Процесс svdsketch следует, чтобы сформироваться, матричный эскиз:

  • svdsketch формирует матричный эскиз итеративно, с каждой итерацией, добавляющей новые столбцы в Q и новые строки к B. Новые столбцы и строки создаются путем извлечения функций из A использование матрицы случайной выборки. Можно управлять количеством столбцов и строк, добавленных в каждой итерации с BlockSize пара "имя-значение".

  • Во время каждой итерации, svdsketch итерации степени использования, чтобы улучшить ортогональность новых столбцов в Q. Можно настроить количество итераций степени с NumPowerIterations пара "имя-значение".

  • Итерации, чтобы сформировать матричную остановку эскиза, когда: количество столбцов в Q и строк в B достигает заданного значения для MaxSubspaceDimension, количество итераций достигает MaxIterations, или относительная ошибка приближения сходится (apxErr <= tol).

  • Улучшить быстроту сходимости, svdsketch может увеличить заданное начальное значение для BlockSize от итерации до итерации, если затухание в apxErr не достаточно.

После матричного эскиза AQB формируется, svdsketch вычисляет сингулярное разложение (SVD) матричного эскиза через [U1,S,V] = svd(B,'econ'), таким образом, что

AQB=(QU1)SVH=USVH.

Если svdsketch может отфильтровать некоторые функции A на основе заданного допуска затем получившиеся факторы SVD содержат меньше сингулярных значений и сингулярных векторов, чем если бы полный SVD выполнялся на A.

Ссылки

[1] Юй, Wenjian, Юй Гу и Яохэнг Ли. “Эффективные Рандомизированные Алгоритмы для Матричного Приближения Fixed-Precision Low-Rank”. SIAM Journal на Анализе матрицы и Приложения 39, № 3 (август 2018): 1339–1359. https://doi.org/10.1137/17M1141977.

Введенный в R2020b