Эта страница переведена с помощью средств машинного перевода. Смотреть оригинал

Гармонические средние итеративно переопределенные наименьшие квадраты для восстановления матриц низкого ранга.

Авторы
ИзданиеarXiv.org.
Год издания2017

 Мы предлагаем новый алгоритм итеративного повторного взвешивания наименьших квадратов (IRLS) для восстановления матрицыXCd1×d2 Рангаrmin(d1,d2) От неполных линейных наблюдений, решения последовательности линейных задач с низкой сложностью. Легко реализуемый алгоритм, который мы называем гармоническим, означает итеративно взвешенные наименьшие квадраты (HM-IRLS), оптимизирует невыпуклый Schatten-p Квази-нормовой санкциониро- вание в целях поощрения низкого ранга и имеет три основные сильные стороны, в частности, для настройки завершения работы матриц. Во-первых, алгоритм сходится глобально к матрице низкого ранга для релевантных, интересных случаев, для которых любой другой (не) выпуклый современный подход к оптимизации не дает восстановления. Во-вторых, HM-IRLS демонстрирует эмпирическую вероятность восстановления, близкую к100% Даже для ряда измерений, очень близких к теоретической нижней границеr(d1+d2r), Т.е.E., Уже для значительно меньшего числа линейных наблюдений, чем любой другой приемлемый подход в литературе. В-третьих, HM-IRLS обнаруживает локально сверхлинейную скорость сходимости (порядка2p), Если линейные наблюдения выполняют подходящее свойство нулевого пространства. В то время как для первых двух свойств мы имеем пока только сильные эмпирические данные, мы докажем третье свойство как наш главный теоретический результат.

 46 страниц, 4 цифры

Ссылка на публикацию
Кüммерле К. , Сиджл Д.   Гармонические средние итеративно переопределенные наименьшие квадраты для восстановления матриц низкого ранга. - : , 2017. // arXiv.org, 2017.
Библиография
1.A. Ахмед и Дж. Ромберг. Компрессионное мультиплексирование коррелированных сигналов. IEEE Transactions on Information Theory, 61 (1): 479--498, 2015.
2.К. М. Р. Audenaert. Обобщение неравенств ценностных величин Мирского. Препринт ArXiv: 1410.4941, 2014.
3.D. S. Бернштейн. Матричная математика: теория, факты и формулы (второе издание). Издательство Принстонского университета, 2009.
4.J. D. Бланшар, Дж. Таннер и К. Вэй. CGIHT: сопряженный градиент итеративного жесткого порогового значения для сжатого зондирования и завершения матрицы. Информация и выводы, 4 (4): 289--327, 2015.
5.E. J. Candes, Y. Эльдар, T. Строхер и В. Воронинский. Фазовый поиск по завершению матрицы. SIAM Journal on Imaging Sciences, 6 (1): 199-225, 2013.
6.E. J. Candes, X. Ли и М. Soltanolkotabi. Фазовый поиск по потоку Wirtinger: теория и алгоритмы. IEEE Transactions on Information Theory, 61 (4): 1985--2007, 2015.
7.E. J. Candes and Y. План. Трудные неравенства оракулов для восстановления матрицы низкого ранга из минимального количества шумных случайных измерений. IEEE Transactions on Information Theory, 57 (4): 2342-2359, апрель 2011 г.
8.E. J. Candes and B. Recht. Точное заполнение матрицы посредством выпуклой оптимизации. Основы вычислительной математики, 9 (6): 717--772, 2009.
9.E. J. Candes, T. Строхер и В. Воронинский. PhaseLift: точное и стабильное восстановление сигнала из измерений магнитуды посредством выпуклого программирования. Сообщения по чистой и прикладной математике, 66 (8): 1241-1274, 2013.
10.Р. Шартрана. Точные реконструкции разреженных сигналов посредством невыпуклой минимизации. IEEE сигнальный процесс. Lett., 14: 707-710, 2007.
11.J. A. Чавес-Домингес и Д. Куцарова. Устойчивость восстановления матриц низкого ранга и его связь с геометрией банахова пространства. Журнал математического анализа и приложений, 427 (1): 320 - 335, 2015.
12.B. Дакорогна. Прямые методы в вариационном исчислении. SpringerVerlag New York, Inc., 1989 год.
13.Я. Добеши, Р. ДеВоре, М. Форнайер и С. G? Unt? Urk. Итеративно восстановленная наименьшая квадратичная минимизация для редкого восстановления. Сообщения о чистой и прикладной математике, 63: 1--38, 2010.
14.J. Давенпорт, Марк А.; Ромберг. Обзор восстановления матриц низкого ранга от неполных наблюдений. Журнал IEEE по отдельным темам обработки сигналов, 10: 608-622, 06 2016.
15.Y. Эльдар, Д. Идейл, и Y. План. Условия уникальности для восстановления матрицы низкого ранга. Appl. Вычисл. Хармон. Анальный., 33 (2): 309-314, 2012.
16.М. Фазель. Минимизация рангов матрицы с приложениями. Кандидатская диссертация, Электротехнический факультет Стэнфордского университета, 2002.
17.М. Форнайер. Численные методы для редкого восстановления. В М. Форнайер, редактор, «Теоретические основы и численные методы для восстановления разреженных», том 9 серии «Радон» по вычислительной и прикладной математике, страницы 93-200. Де Грюйтер, Берлин, 2010.
18.М. Fornasier, S. Питер, Х. Раухут и С. Червь. Сопряженное градиентное ускорение итеративно-взвешенных методов наименьших квадратов. Вычислительная оптимизация и приложения, стр. 1-55, 2016.
19.М. Форнайер, H. Раухут и Р. Уорд. Матричное восстановление низкого ранга путем итеративно-взвешенной минимизации наименьших квадратов. Журнал SIAM по оптимизации, 21 (4): 1614-1640, 2011. [Используя алгоритм IRLS-FRW (IRLS-M), код из https: // github.Ru / rward314 / IRLSM].
20.S. Фукарт. Вогнутое неравенство Мирского и восстановление низкого ранга. Http: // www.Математика.Таму.Edu / foucart / publi / Mirsky.Pdf, ~ preprint, 2016.
21.S. Фукарт и Х. Раухут. Математическое введение в сжатие. Прикладной и численный гармонический анализ. Springer New York, 2013.
22.Y. Гао, Дж. Пэн, С. Юэ и Й. Чжао. О свойстве нулевого пространства минимизации l q при 0 <q = <1 в сжатом зондировании. Журнал функциональных пространств, 2015: 4203--4215, 2015.
23.Я. Гохберг, С. Голдберг и Н. Крупник. Следы и детерминанты линейных операторов, том 116. Springer, 2012.
24.D. Голдберг, Д. Николс, Б. М. Оки и Д. Терри. Использование совместной фильтрации для создания информационного гобелена. Сообщения ACM, 35 (12): 61-70, 1992.
25.D. Валовой. Восстановление матриц низкого ранга из нескольких коэффициентов в любом базисе. IEEE Transactions on Information Theory, 57 (3): 1548-1566, 2011.
26.D. Гросс, Ф. Krahmer, R. Kueng. Частичная дерандомизация фазелифта с использованием сферических конструкций. Journal of Fourier Analysis and Applications, 21 (2): 229-266, 2015.
27.D. Гросс, Й.-K. Лю, С. T. Flammia, S. Беккер и Дж. Эйзерт. Квантовая томография состояния с помощью сжатого зондирования. Physical Review Letters, 105: 150401, 2010.
28.J. П. Халдар и Д. Эрнандо. Ограниченные по рангу решения линейных матричных уравнений с использованием степенной факторизации. IEEE Signal Processing Letters, 16 (7): 584-587, июль 2009 г. [Используя алгоритм pMCAltMin (Alternating Minimization), частичный код доступен по адресу http: // mr.Usc.Edu / download / irpf /].
29.N. Halko, P. Г. Мартинссон и Дж. A. Tropp. Поиск структуры со случайностью: вероятностные алгоритмы построения приближенных матричных разбиений. SIAM Review, 53 (2): 217-288, 2011.
30.П. Джейн, Р. Мека и я. S. Dillon. Гарантированная минимизация ранга с помощью прогнозирования сингулярных значений. В J. D. Lafferty, C. К. Я. Уильямс, Дж. Shawe-Taylor, R. S. Земель и А. Калотта, редакторы, Достижения в системах обработки нейронной информации 23, pages 937--945. Curran Associates, Inc., 2010.
31.П. Jain, P. Нетрапали и С. Сангхави. Завершение низкоуровневой матрицы с использованием альтернативной минимизации. В трудах сорок пятого ежегодного симпозиума АСМ по теории вычислений, STOC 13, страницы 665--674, Нью-Йорк, Нью-Йорк, США, 2013 год. ACM.
32.A. Джеймсон. Решение уравнения ax + xb = c путем обращения матрицы m x m или n x n. SIAM Journal on Applied Mathematics, 16 (5): 1020-1023, 1968.
33.М. Кабанава, Р. Kueng, H. Раухут и У. Terstiege. Стабильное восстановление матрицы низкого ранга через свойства нулевого пространства. Информация и выводы: журнал IMA, 5 (4): 405, 2016.
34.A. Кириллидис и В. Чевер. Матричные рецепты для методов жесткого ограничения. Journal of Mathematical Imaging and Vision, 48 (2): 235-265, 2014. [Используя алгоритм Matrix ALPS II (Matrix ALgrebraic PursuitS II), код из http: // akyrillidis.Github.Io / projects /].
35.Z. Лю, А. Hansson и L. Ванденберг. Идентификация ядерной нормативной системы с недостающими входами и выходами. Systems & Control Letters, 62 (8): 605 -612, 2013.
36.Z. Лю и Л. Ванденберг. Внутренний метод аппроксимации ядерной нормы с применением к идентификации системы. Журнал SIAM по анализу и применению матриц, 31 (3): 1235-1656, 2010.
37.J. Магнус и Х. Neudecker. Матричное дифференциальное исчисление с приложениями в статистике и эконометрике. Wiley серии в теории вероятностей и статистики: тексты и ссылки. Wiley, 1999.
38.B. Мишра, Г. Мейер, Ф. Бах и Р. Гроб Господень. Оптимизация низкого ранга с нормой штрафа трассировки. Журнал SIAM по оптимизации, 23 (4): 2124-2149, 2013.
39.К. Мохан и М. Фазель. Итерационные взвешенные алгоритмы минимизации матричного ранга. Журнал «Исследование машинного обучения», 13 (1): 3441--3473, 2012. [Используя алгоритм IRLS-MF (IRLS-p), код из https: // faculty.Вашингтон.Edu / mfazel /].
40.S. Оймак К. Мохан, М. Фазель и Б. Хассиби. Упрощенный подход к восстановлению для матриц низкого ранга. В 2011 году Международный симпозиум IEEE по вопросам теории информации, ISIT 2011, St. Петербург, Россия, страницы 2318-2322, 2011.
41.D. Парк, А. Kyrillidis, C. Караманис и С. Сангхави. Нахождение низкоуровневых решений матричных задач эффективно и надежно. Препринты ArXiv: 1606.03168, июнь 2016 года. [Используя алгоритм BFGD (Bi-Factored Gradient Descent), код из http: // akyrillidis.Github.Io / projects /].
42.D. Pimentel-Alarc? N, N. Бостон и Р. D. Новак. Характеризация детерминированных шаблонов выборки для завершения матриц низкого ранга. Препринты ArXiv: 1503.02596, 2015.
43.B. Recht, M. Фазель и П. A. Паррило. Гарантированные решения минимального ранга линейных матричных уравнений посредством минимизации ядерной нормы. SIAM Review, 52 (3): 471-501, 2010.
44.B. Recht, W. Сюй и Б. Хассиби. Нулевые пространственные условия и пороги для минимизации ранга. Математическое программирование, 127 (1): 175-202, 2011.
45.E. Шост и П.-J. Spaenlehauer. Квадратично сходящийся алгоритм для структурированного низкоуровневого приближения. Основы вычислительной математики, 16 (2): 457--492, 2016.
46.N. Сребро, Дж. Ренни и Т. S. Яаккола. Максимальное разграничение матриц матрицы. В L. К. Саул, Y. Вайс и Л. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 1329-1336. MIT Press, 2005.
47.М. Стюарт. Возмущение СВД при малых сингулярных значениях. Линейная алгебра и ее приложения, 419 (1): 53 - 77, 2006.
48.J. Sun, Q. Qu и J. Райт. Когда невыпуклые проблемы не страшны? Препринт ArXiv: 1510.06096, 2015.
49.Р. Солнце и З. Q. Ло. Гарантированное завершение матриц посредством невыпуклой факторизации. В Основах информатики (FOCS), 2015 IEEE 56-й ежегодный симпозиум по основам информатики, страницы 270--289, 2015.
50.J. Таннер и К. Вэй. Нормализованное итеративное жесткое пороговое значение для завершения матрицы. SIAM Journal on Scientific Computing, 35 (5): S104 - S125, 2013.
51.J. Таннер и К. Вэй. Матричное заполнение низкого ранга чередующимися методами наискорейшего спуска. Applied and Computational Harmonic Analysis, 40 (2): 417 - 429, 2016. [Используя алгоритм ASD (Alternating Steepest Descent), код из https: // www.Математика.Ucdavis.Edu / kewei / publications.Html resp. Https: // www.Математика.Ucdavis.Edu / kewei / code / mc20140528.Tar]. ~ ~
52.S. Ту, Р. Бочар, М. Симховиц, М. Soltanolkotabi и B. Recht. Низкоширокие решения линейных матричных уравнений через поток Прокрустей. Препринт ArXiv: 1507.03566, 2015.
53.С. F. Ван займ. Вездесущий продукт Кронекера. Journal of Computational and Applied Mathematics, 123 (12): 85 - 100, 2000.
54.B. Vandereycken. Матричное низкоуровневое заполнение с помощью римановой оптимизации. Журнал СИМА по оптимизации, 23 (2): 1214-1236, 2013. [Используя алгоритм RiemannOpt («Риманова оптимизация»), код с http: // www.Unige.Ch / math / vandereycken / matrix_completion.Html].
55.П.-? A. Wedin. Границы возмущений в связи с разложением по сингулярным числам. BIT Численная математика, 12 (1): 99-111, 1972.
56.К. Вэй, Дж.-F. Цай Т. F. Чан и С. Леунг. Гарантии римановой оптимизации для завершения матриц низкого ранга. Препринт ArXiv: 1603.06610, 2016.
57.К. Вэй, Дж.-F. Цай Т. F. Чан и С. Леунг. Гарантии римановой оптимизации для восстановления матрицы низкого ранга. SIAM J. Матричный анал. Appl., 37 (3): 1198-1222, 2016.
58.Z. Вэнь, W. Инь и Я. Чжан. Решение модели факторизации низкого ранга для пополнения матрицы нелинейным последовательным алгоритмом релаксации. Математическое программирование, 4 (4): 333--361, 2012.
59.Q. Чжэн и Дж. Лафферти. Сходящийся алгоритм градиентного спуска для минимизации ранга и полуопределенного программирования из случайных линейных измерений. В C. Кортес, N. D. Лоуренс, Д. D. Ли, М. Сугияма и Р. Гарнетт, редакторы, Достижения в системах обработки нейронной информации 28, страницы 109-117. Curran Associates, Inc., 2015 год.
60.Q. Чжэн и Дж. Лафферти. Анализ сходимости для завершения прямоугольной матрицы с использованием факторизации Бюрера-Монтейро и градиентного спуска. Препринт ArXiv: 1605.07051, 2016.

Эта публикация на других ресурсах

Портал arXiv.org

Другие публикации этой тематики
1.URV-факторизация со случайным смещением ортогональной системы
Беккер С. , Фолбертх Д. , Джриджори Л.
2.Распределенный и инкрементальный алгоритм SVD для анализа агломерационных данных на больших сетях
Ивен М. А., Ондж Б. В.
3.Сходимость альтернативных методов наименьших квадратов для приближения первого порядка к тензорам высокого порядка
Еспидж М. , Кхакхатруан А. М.
4.Эффективные алгоритмы для CUR и интерполяционных матричных разложений
Воронин С. , Мартинссон П. Д.
5.Быстрое восстановление и аппроксимация скрытой структуры Коши
Лиесен Д. , Луке Р.
6.Регулярное редактирование краев "Plug-and-Play"
Кхен Д. , Килмер М. Е., Пер К. Х.
7.Вклад в номер условия общей задачи наименьших квадратов
Джиа З. , Ли Б.
8.Восстановление матрицы низкого ранга посредством итерационно-взвешенной минимизации наименьших квадратов
Форнасиер М. , Раухут Х. , Вард Р. Е.
9.Введение в суммарные наименьшие квадраты
10.GPGCD, итерационный метод для вычисления приближенного GCD одномерных многочленов, с комплексными коэффициентами
Теруи А.