Luận án: Phục hồi tín hiệu cấu trúc trong không gian chiều cao bằng tối ưu hóa lồi phi trơn

Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis Thesis by Christos Thrampoulidis In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy CALIFORNIA INSTITUTE OF TECHNOLOGY Pasadena, California 2016 Defended May 17, 2016 ii c 2016 Christos Thrampoulidis ORCID: [0000-0001-9053-9365] All rights reserved except where otherwise noted iii ACKNOWLEDGEMENTS “As you set out for Ithaka hope the voyage is a long one, full of adventure, full of discovery.) Wise as you will have become, so full of experience, you will have understood by then what these Ithakas mean. Admittedly, the journey to this thesis has not been a paved way; it has gone through difficult and sometimes lonely paths, and it has been full of ups and downs. How- ever, during these five years I have been extremely lucky to have been surrounded by wonderful people -mentors, colleagues, friends, family- that have helped me the most in all aspects. It is thanks to them that “this voyage has been full of adventure, full of discovery and full of experience", and that I have grown both as a person and as a researcher.

This is an opportunity to recognize my appreciation to them. First, I would like to express my gratitude to my advisor Prof. Babak Hassibi for his kindness, generosity, and patience; for the unstressful work environment and the academic freedom that he has provided me with, and for the guidance through- out this journey. His brightness, his enthusiasm, his clarity of thought, and his ability to communicate complex concepts -from a very diverse set of fields- in the most transparent ways have been an enormous inspiration.

His provocative ques- tions and careful criticism have taught me to see the bigger picture, not only when presenting my work, but also as a guidance to new directions. His constant en- couragement has helped me grow confidence as a researcher. I am also grateful for several thought-provoking and always intriguing non-technical discussions, and for the opportunities he has provided me to travel and attend a number of conferences held all around the world. Next, gratitude is extended to the rest of the members of my thesis committee: Pro- fessors P.

Vaidyanathan, Joel Tropp, Adam Wierman, and Venkat Chandrasekaran, for their time, advice, and critical evaluation of my thesis. I would like to express special thanks to Professors Vaidyanathan and Tropp for their encouragement, sup- port, and advice that also extended beyond research to career planning. I am thank- ful to Prof. Vaidyanathan for his kindness and friendliness during our everyday encounters and short discussions in the hallways of the Moore Laboratory.

I thank Joel Tropp for some of the most useful, enriching and stimulating courses that I have taken at Caltech; I will always admire and be inspired by his remarkable pro- iv foundness, clarity and simplicity in teaching and in presenting his work. I feel indebted to all my collaborators: Samet Oymak, Subhmonesh Bose, Ehsan Abbasi, Ashkan Panahi, Weiyu Xu, Linqi (Daniel) Guo, Kishore Jaganathan, and Navid Azizan, for their patience, for all the things that I learnt from them, and for all the fun and long hours that we spent thinking and learning together! Some of the major contributions and ideas of this thesis developed during long whiteboard discussions with Samet, Ehsan, and Ashkan. Thanks to Samet for introducing me to many of the problems addressed in this thesis. His unique combination of fast problem-solving skills, of hard work and of constant enthusiasm always inspired me.

I also have some very good memories with Samet during our trip in Hawaii for ISIT. Thanks to Ehsan for all the technical work that we accomplished together. But even more so, I wish to thank him for his support and encouragement, for his endless patience, for being a great listener and a good friend. Thank you Ehsan, for the always pleasant and fun overnight shifts in the lab, for the handy Persian expressions that you taught me, for our amazing trip to Chicago, and for all the stories we shared together.

Thanks to Ashkan and Daniel for our (rather) short but very productive collaboration. Thanks to Weiyu for helpful discussions and encouraging feedback. The works that we did together with Bose, Kishore, and Navid are not part of this thesis, but are by no means less important. Bose had the difficult task to be my first collaborator and coauthor.

I am grateful to him for his patience, for teaching me the importance of communicating research results in a transparent way, and for his advice during the multiple times that I felt lost. Thanks to Κισώρος (cf., Kishore) for our joint work that led us win the Qualcomm Innovation Fellowship. I always admire his patience and calmness, and I confess that I sometimes laugh at his “jokes"! My collaboration with Navid has been only very recent, but one of the most pleasant ones, and I wish it continues. Many thanks go to all my labmates over these five years for the things that they have taught me, and for our fascinating conversations! Thanks to the “older generation": Amin, Teja, Wei, Samet, Bose and Ahn.

Special thanks to Amin Khajehnejad for introducing me to the culture of the lab when I first arrived at Caltech, and for teaching me many useful things (including, but by no means limited to, access to free food). Thank you to Matt, Kishore, Wael, Ramya, Ehsan, Navid, James, Anatoly, and Fariborz for creating an especially friendly and pleasant environment in the lab during the last two years. Thank you for your support, for putting up with my strange habits (yes, you may now take the clock and put it back on the wall), v and for being great listeners to my everyday complaints. I would especially like to express my gratitude to my good friend Wael, whom I have known since my very first days at Caltech.

Also, thank you to all other students in Caltech’s Electrical Engineering and Ap- plied Mathematics Departments for friendly interactions, advice and intriguing dis- cussions. Special thanks go to Roarke, Mark, Richard, and Yong Sheng. I would also like to thank the secretarial staff for putting up with me and answering all my questions: Shirley, Tanya, Katie, Anne, Terecita, and Lucinda. My thanks also ex- tend to the friendly, welcoming, and always smiling administrative staff at Caltech’s International Student Programs Office and at Chandler Café.

Outside Caltech, I am grateful to Professors G. Fassois from the University of Patras for their motivation and support when applying for graduate studies in the US. I am especially thankful to Prof. Moustakides for being a wonderful advisor during my undergraduate years, but also for the constant encouragement and guid- ance that I have been receiving from him since then.

My gratitude extends to Prof. Toumpakaris for selflessly putting on long hours to help me complete my applica- tion files. I would also like to thank the “Andreas Mentzelopoulos Scholarships for the University of Patras" for supporting my studies during my first year at Caltech. A very special thank you belongs to my teacher Mr.

Dimitris Aretakis and to my friend Stefanos Aretakis for teaching me and for making me love math. Thank you to my very first international friends at Caltech: Aleksander, Christophe, Wael, Krishna, Mark, and Roarke, who have helped me the most during the intense first-year of courses, and with whom I have some awesome stories to remember. Thanks to the Greeks at Caltech and at JPL for all the fun and relaxing moments: for our loud lunches at Chandler, for the unforgettable “Vassilopita" nights, and for our everyday loud conversations and jokes at Caltech’s gym. Special thanks to Costas S., Theodore, Christos, Costas A., Marilena, and Vassilis for being the first ones to welcome me at Caltech.

Thanks to my friend Dimitris for being the best host during my visits in Chicago! Thanks to my conference-travel buddy Nicoló for some unforgettable nights, whether at Hong-Kong or at Urbana-Champaign. I would also like to thank my friends back in Greece for all the fun and relaxing mo- ments during my summer visits over there. Thank you to my childhood friends in Kastellokampos. Special thanks to Evangelia, Costas, and Nikos for their encour- agement.

vi Among the many wonderful people that I have met during this journey, I would like to especially acknowledge Panagiotis Vergados, Juan Andrés Muniz, Wael Hal- bawi and Georgia Papadakis, who have been great friends and have kept me sane and happy over the years. Thank you for your honesty, for your kindness, and for caring for me not only when the sun is shining, but most importantly during the storms. (Yes, there were storms despite the California weather!) Thank you for all the memories that we have shared; thank you for every single day. Panagiotis, ad- ditional thanks go to you for the long hours that you selflessly put on proofreading parts of this thesis and providing invaluable feedback on my thesis presentation! I am also thankful to my extended family in Veroia, Ptolemaida, Thessaloniki and Patras for always being there for me, for their love, and for their heartfelt support during all these years.

Thank you for always cutting a cake for my birthday even if I had to blow out the candles and eat my piece of it over Skype! Finally, my deepest gratitude belongs to my family: to my father Kleanthis, whose dignity, diligence and ambition are a constant source of inspiration to me; to my mother Vassiliki, whose positive energy and kindness are a constant reminder to always smile; and to Manolis, the best and most caring brother in the world. I have no words to thank you for your unconditional love, for all my sweet memories, for all the values that you have taught me, for all that I am and that I have ever accomplished, but to dedicate this dissertation to you. vii To my parents Vassiliki and Kleanthis, and to my brother Manolis. viii ABSTRACT The typical scenario that arises in modern large-scale inference problems is one where the ambient dimension of the unknown signal is very large (e., high-res- olution images, recommendation systems), yet its desired properties lie in some low-dimensional structure such as, sparsity or low-rankness.

In the past couple of decades, non-smooth convex optimization methods have emerged as a powerful tool to extract those structures, since they are often computationally efficient, and also they offer enough flexibility while simultaneously being amenable to perfor- mance analysis. Especially, since the advent of Compressed Sensing (CS) there has been significant progress towards this direction. One of the key ideas is that random linear measurements offer an efficient way to acquire structured signals. When the measurement matrix has entries iid from a wide class of distributions (including Gaussians), a series of recent papers have established a complete and transparent theory that precisely captures the performance in the noiseless setting.

In the more practical scenario of noisy measurements the performance analysis task becomes significantly more challenging and corresponding precise and unifying re- sults have hitherto remained scarce. The available class of optimization methods, often referred to as regularized M-estimators, is now richer; additional factors (e., the noise distribution, the loss function, and the regularizer parameter) and sev- eral different measures of performance (e., squared-error, probability of support recovery) need to be taken into account. This thesis develops a novel analytical framework that overcomes these challenges, and establishes precise asymptotic performance guarantees for regularized M-esti- mators under Gaussian measurement matrices. In particular, the framework al- lows for a unifying analysis among different instances (such as the Generalized LASSO, and the LAD, to name a few) and accounts for a wide class of perfor- mance measures.

Among others, we show results on the mean-squared-error of the Generalized-LASSO method and make insightful connections to the classical the- ory of ordinary least squares and to noiseless CS. Empirical evidence is presented that suggests the Gaussian assumption is not necessary.