Сжатие данных с помощью сингулярного разложения матрицы

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

Вырожденные задачи наименьших квадратов

Сжатие данных с помощью сингулярного разложения матрицы

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

План

Лекция 30.Использование сингулярного разложения матрицы для решения различных задач

Питання

1. Який ряд називається рядом з додатними членами?

2. Критерій збіжності рядів з додатними членами.

3. Перша ознака порівняння збіжності рядів в формі нерівностей.

4. Перша ознака порівняння в граничній формі.

5. Друга ознака збіжності рядів з додатними членами.

6. Ознаки Коші та Даламбера збіжності рядів з додатними членами в формі нерівностей і в граничній формі.

7. Визначення невластивого інтеграла І роду.

8. Інтегральна ознака Коші-Маклорена збіжності рядів з додатними членами.

Пусть даны -матрица и -вектор . Линейная задача наименьших квадратов заключается в отыскании -вектора , минимизирующего величину (евклидова норма вектора ). Если и матрица невырожденная, то решением задачи является вектор (т.е. решение СЛАУ ). Если , т.е. число уравнений больше числа неизвестных, то задача называется переопределенной; в этом случае, ввобще говоря, не существует вектора , точно удовлетворяющего системе . Иногда встречаются и недоопределенные задачи, где .

Пример. Аппроксимация данных является традиционным приложением метода наименьших квадратов. Пусть даны пар чисел . Предположим, что мы хотим найти кубический полином, который бы «наилучшим образом» представлял числа как функцию от . Это означает, что коэффициенты многочлена третьей степени , нужно определить так, чтобы многочлен

минимизировал невязку для , т.е. перед нами стоит задача минимизации вектора

,

где и - векторы длины , - матрица размера , а - вектор длины 4. Для минимизации можно выбрать любую норму, например, , или . В последнем случае получаем задачу наименьших квадратов, она соответствует минимизации сумм квадратов невязок: .

Пример. В статистическом моделировании часто приходится оценивать некоторые параметры , основываясь на наблюдениях, «загрязненных» шумом. Предположим, например, что в рамках компании по приему в университет желательно предсказать средний бал будущего обучения в нем, исходя из среднего бала , который абитуриент имел в старших классах школы, и результатов двух экзаменов (тестов): устного и письменного . Основываясь на прошлых данных для ранее принятых студентов, можно построить линейную модель вида

.

Наблюдениями являются четверки чисел , , и , по одной для каждого из студентов в базе данных. Итак, желательно минимизировать величину

,

что можно рассматривать как задачу наименьших квадратов.

Рассмотрим решение задачи наименьших квадратов при помощи сингулярного разложения матрицы.

Напомним, что спектральная матричная норма матрицы опрелеляется следующим образом:

,

где символ обозначает максимольное собственное значение матрицы . Если матрица - вещественная симметричная, то , и тогда

.

Утверждение 1. Для спектральной матричной нормы верно равенство

, (1)

где - любые ортогональные матрицы.

Можно показать, что если - невырожденная матрица с сингулярным разложением , то решением задачи минимизации является вектор

.

Действительно:

Обозначим в последнем выражении: , тогда получим:

.

Минимальное значение , а значит и достигает тогда, когда все неотрицательные слагаемые в правой части последнего равенства равны 0:

(2)

Поскольку - невырожденная матрица, у нее нет нулевых сингулярных чисел, это значит, что мы можем однозначно определить из (2) :

. (3)

Подставим в (3) выражения , получим:

,

откуда , что и требовалось доказать.

Пусть для матрицы имеется сингулярное разложение .

Теорема. Если , где , - столбцы матрицы , а , где , - столбцы матрицы , сингулярное разложение матрицы можно представить в форме внешних произведений:

,

т.е. в виде суммы матриц , ранга 1. Тогда ближайшая к (в смысле спектральной матричной нормы ) матрицей ранга является матрица

,

называемая малоранговой аппроксимацией матрицы (или аппроксимацией матрицы ранга ), причем

.

Для матрицы справедливо также представление

,

где .

Приведенная теорема используется для сжатия изображений. Изображение размера - это попросту матрица, элемент которой интерпретируется как яркость точки (пикселя) . Другими словами, элементы матрицы, изменяющиеся от 0 до 255, интерпретируются как точки с окраской от черной (что соответствует 0) до белой (что соответствует 255) с различными промежуточными степенями серого цвета (возможны и цветные изображения, тогда там будут фигурировать 3 матрицы). Вместо того, чтобы хранить или передавать все элементов матрицы, представляющей изображение, часто бывает предпочтительным сжатие этого изображения, т.е. хранение гораздо меньшего массива чисел, с помощью которых исходный образ все же может быть приближенно восстановлен. Проиллюстрируем это на примере изображения размером (рис.1), матрицу которого обозначим . При построении сингулярного разложения матрицы этого изображения будет вычислено 480 СНЧ. Согласно предыдущей теоремы матрица есть наилучшее приближение ранга матрицы в том смысле, что она реализует минимум величины . Заметим, что для восстановления матрицы требуется лишь слов памяти, в которых хранятся векторов длины и векторов длины . В то же время дляхранения (или той же матрицы , но в явном виде) нужны слов, т.е. гораздо большая память при малом . Будем рассматривать как сжатое изображение, хранимое с помощью слов памяти. Эти приближенные изображения для различных значений приведены на рис.2,3. Выигрыш в памяти здесь составит . Результаты эксперимента приведены в табл.1.

Таблица 1 -

Коэффициент малоранговой аппроксимации	Выигрыш в памяти при использовании малоранговой аппроксимации

Рис.1. Исходное изображение

Рис. 2. Сжатое изображение. Ранг аппроксимации равен 20

Рис. 3. Сжатое изображение. Ранг аппроксимации равен 160

Дата добавления: 2014-01-04