先利其器 :高維隨機矩陣

本文主要介紹了高維隨機矩陣的兩方面性質：譜分佈的極限性質與非漸進隨機矩陣。但是對於譜分佈的極限性質，並沒有涉及很多，主要是大概瞭解一下都是用什麼工具做的，大致有哪些結論。對於非漸進隨機矩陣也是如此。

最開始見到隨機矩陣依然是在Vershynin中（他的這本書真是涉及了很多方面，從去年大概十月份第一次讀到現在，已經不知道讀了多少遍了……），覺得蠻有趣，當時就找了Tao的Topics in random matrix theory來讀，然而並不能讀得懂，就一直擱置了。後來發現在Learning Theory中還真有一些用隨機矩陣來做的工作，如Couillet做的譜聚類的工作蠻有趣（他的學生廖振宇（也在知乎）做的似乎也蠻有趣，不過還沒有怎麼深入的瞭解，打算接下來讀一讀），週六去東北師範大學（題圖就是當時在東北師範大學拍的）聽了David P。 Woodruff的報告，是關於Tensor Low Rank Approximation的，其中有一步用i。i。d。的Gaussian Random Matrix對（以三階張量為例）Flat（按照三個維度的兩兩組合得到的三種Flat）之後的矩陣進行隨機化（以右乘這個隨機矩陣的方式），然而看起來也只是起到了隨機化的作用，沒有用到什麼隨機矩陣的實質結論。話說回來，Matrix Recovery ， Low Rank Approximation 還真是個蠻熱門的方向，之後有時間也希望瞭解一下。

幸好在Learning Theory 中用到的隨機矩陣，不是那種類似於Tracy-Widom Distribution的（比較主流的）隨機矩陣，那種隨機矩陣我認為太理想了，性質太好了，以至於不是很現實。不過，用這種手段解決組合問題，是蠻有趣的。不知道有沒有可能作為一種手段在TCS中應用到，之前看到了一個問題是Sparse Perceptron的學習（Feldmen在COLT 2014上提出的Learning Half Spaces的Statistical Query Complexity這個Open Problem，當然我還沒看有沒有人解決，因為對很TCS的這種Computational Learning Theory不是很感興趣，所以還不知道要不要要做這個方向（不是直接放棄的原因是，可能因為接觸的少，思維還很“數學”（然而我的數學實在是太菜了），所以還不習慣這個學科，怕太草率了），因此以後還可能會看一看）。因此我對於隨機矩陣這裡的學習，是想著“如何能夠從工具的角度掌握”，即如何從實際問題中意識到：這個問題也許可以透過隨機矩陣來解決？保留這樣一種可能性，至於使用這個工具的能力，還是要留著真的需要用到的時候，再回來補充。