Processing math: 100%

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

Авторы
Издание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