色々勉強中．基底追跡について，まだまだ理解が足りない気もするがまとめてみる．
DCTやウェーブレットを使った次元圧縮問題を考える．
Ax=b
x,bはそれぞれn次元ベクトル，Aはn×n行列であるとする．
Aを仮にDCTを表す直交基底行列とすると，上の式は原信号xをDCTした信号bを得る事を意味している．bの値が大きい時，それは原信号xがその周波数成分を大きく持つ事になる．そのため，最も単純な次元圧縮方法は，bの絶対値abs(b)が大きいものを上位k個選び，その他の値を0としたb_hatを逆変換すれば良い．
b_hat = b if abs(b) > b_thresh or 0 otherwise
x_hat = A^{-1}b
ここで，b_threshはk番目にabs(b)が大きいbの値，A^{-1}はAの逆行列を表す．
DCTのような直交基底を用いた次元圧縮は，原信号のエネルギーが低周波に集まる(信号が滑らか)事を仮定しているため，インパルスノイズに弱い．
ちょっと違う視点で考えてみると，DCTを表す直交行列は周期関数に適した信号のための基底行列であるため，インパルスノイズを含む信号には対応出来ないというわけ．
過完備基底を用いた基底追跡の根本的な考えは，変換行列に色々な信号に適した行列を含めてしまおうというもの．
ここで，
Bx=y
という問題を考える．原信号xはn次元ベクトルであるが，yはm次元ベクトル(m>n)，Bはm×n行列となる．このような過剰な基底(過完備基底)を使うと，yをユニークに求められなくなるので，yは出来るだけスパースな信号で表せるという仮定を置く事で以下の最小化問題に帰着できる．
minimize |Bx-y|2
subject to |y|1
では，どのようなBを選べば良いかというと，例えばB=A|Iというように，DCTを表す直交行列と単位行列を組み合わせると，Aの部分が滑らかな信号を，Iの部分がインパルスノイズをそれぞれ表す事となる．
このように，過完備基底を使う事でインパルスノイズを持つ信号の圧縮も行える．
