ランダムプロジェクションとスパースネス

鈴木 大慈
東京大学情報理工学系研究科
数理情報学専攻2010/7/16→7/26
1• Compressed Sensing (CS) - encoding– ランダムプロジェクション
– Johnson–Lindenstrauss Lemma[Candes, Romberg, and Tao: Robust uncertainty principles: Exact signal
reconstruction from highly incomplete frequency information.
IEEE Trans. on Information Theory, 52(2) pp. 489 - 509, 2006][Donoho: Compressed sensing.
IEEE Trans. on Information Theory, 52(4), pp. 1289 - 1306, April 2006) ]• Lasso & Dantzig Selector – decoding– スパース表現のリカバリー

2Compressed Sensing (CS)=d-sparse[Logan-Shepp phantom]

ランダムRandom Sampling

Gaussian, Bernoulli, Hadamard matrix,…

3

Decoding (L1-minimization)[Candes, Romberg, and Tao: Robust uncertainty principles: Exact signal
reconstruction from highly incomplete frequency information.
IEEE Trans. on Information Theory, 52(2) pp. 489 - 509, 2006]
4応用例：顔識別[Wright, Yang, Ganesh: Robust Face Recognition via Sparse Representation.
IEEE TRANS. PAMI, vol. 31, no. 2, February 2009]

余談 一方、カリフォルニア大学バークレー校の工学部学部長を務めるShankar Sastry氏
が指摘するように、Yang氏の新しい顔認識アプローチは、この分野における何年もの研究を用なしにしてしまうものでもある。
「研究者たちは本当に困惑している。あんまりではないか。顔のどの部分の特徴を選ぼうが構わない？ これは長年の研究と真っ向から対立するものだ」と、Sastry氏は述べた。
5[Wired Vision, WIRED NEWS]必要なサンプル数
d: 真の非ゼロ成分の数
M: featureの次元
n：サンプル数 （ランダムサンプリング）n

サンプル数がを満たすなら，確率真が正確に再現されるで．

ランダムサンプリングn×M

6

本日のメインJohnson–Lindenstrauss Lemma• W. Johnson and J. Lindenstrauss: Extensions of Lipschitz mappings
into a Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• S. Dasgupta and A. Gupta: An Elementary Proof of a Theorem ofJohnson and Lindenstrauss. Random Structures and Algorithms,22(1):60--65, 2003.

[http://www-users.math.umd.edu/~nstrawn/oralprelim.pdf]

78

J–L Lemma for CS• R. Baraniuk, M. Davenport, R. DeVore, M. Wakin: A Simple Proof of
the Restricted Isometry Property for Random Matrices. ConstructiveApproximation, 28(3), pp. 253-263, December 2008.のようにおく．
d次元空間に詰め込めるδボールの数 × d次元空間の数

9Back to CS
for all d-sparse x.

:Ristricted Isometry

Theorem 3.

[Emmanuel Candès: The restricted isometry property and its
implications for compressed sensing. Compte Rendus del'Academie des Sciences, Paris, Series I, 346, pp. 589-592, 2008]

Ifsatisfies
recovers the truth exactly:

with, then CS,
for all d-sparse x0.

10

応用例2
• D. Hsu, S. Kakade, J. Langford & T. Zhang: Multi-Label Prediction
via Compressed Sensing. NIPS2009.

Multi-Label

regression

M:超大 (22000)
しかしd-sparseでdは小さい(4).

sparse recovery

11Lasso&Dantzig Selector(雑音あり)

12

Condition for Lasso Analysis[Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso andDantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009]：Restricted eigenvalue condition

十分条件

Iの中と外で相関低い
かつ列フルランク13

Convergence Rate of Sparse Learning– Candes & Tao: AS2007 (Dantzig selector)– Bunea, Tsybakov & Wegkamp: AS2007 (Lasso)– Meinshausen & Yu: AS2009 (Lasso)– Bickel, Ritov & Tsybakov: AS2009 (Dantzig&Lasso)– Raskutti, Wainwright & Yu: arXiv:0910.2042, 2009.
minimax rate
14

関連研究
• Gunnar Martinsson:“Randomization: Making Very Large-Scale Linear Algebraic
Computations Possible”
NIPS 2009 turorial→ 大きな行列をrandom projectionで小さな行列に落としてSVDrandom proj.

A15

Multiple Input

Multiple Output•multi-label•various tasks•high dimension•huge data

random projection

Low dimensional
representation

16

今後の展開？
• 圧縮 ⇔ Hashing• 座標変換への不変性• Non-sparse• 深い理論と広い応用？

17