ランダムな巡回行列の作用素ノルムの上限

math

すっきりと解決したのでメモ.

  1. {-1,0,+1}要素のランダムなn次元ベクトル (c_0,...,c_{n-1}) を考えて対応する巡回行列を確率変数としてP_nとおく.
  2. l_2-ノルムに対応する作用素ノルムの上限は固有値の絶対値の上限に等しい. (n次正方行列を考えるので.)
  3. 巡回行列はフーリエ行列で対角化可能で, 固有値は\sum_{k=0}^{n-1} c_k \exp(- 2 \pi i m k/n) (m=0,...,n-1).
  4. よってこの固有値の最大を求めればよい.
  5. Hoeffdingの上界より, ある固有値の絶対値が\sqrt{n} \omega(\sqrt{\log{n}})以下である確率は1-2^{-\omega(\log{n})}以上.
  6. Union bound取って, 全ての固有値の絶対値が同様である確率は1-n2^{-\omega(\log{n})}以上.

という寸法かー. 巡回行列以外に一般化するのは面倒臭そう. cyclicじゃなくてnegacyclicくらいならフーリエ行列もどきで対角化出来るので同様の議論が可能.

一般のランダム行列の場合は, もうちょい良いバウンドが知られていて, 適当な定数Cを取ってC√nにで同様の議論が可能ってのが羨ましい. 対称Toeplitz行列の場合はMark W. Meckes “On the spectral norm of a random Toeplitz matrix” (Electronic Communications in Probability 12 (2007), 315--325) ってのがi.i.d.からちょっとだけ緩めた場合の良い上界を与えているそうだ. 概要だけ読んだ.

  翻译：