Bilateral Random Projections

Reminded of it thanks to Sergey, here is the simple but powerful:

Bilateral Random Projections by Tianyi Zhou, Dacheng Tao. The abstract reads:

Low-rank structure have been profoundly studied in data mining and machine learning. In this paper, we show a dense matrix X’s low-rank approximation can be rapidly built from its left and right random projections Y_1 = XA_1 and Y_2 = X^T A_2, or bilateral random projection (BRP). We then show power scheme can further improve the precision. The deterministic, average and deviation bounds of the proposed method and its power scheme modification are proved theoretically. The effectiveness and the efficiency of BRP based low-rank approximation is empirically verified on both artificial and real datasets.

Here is a small and simple implementation of it.

clear
% X is an mxn low rank matrix
m= 100;
n= 20;
r = 20;
q = 30;
X = rand(m,n);
%
%
A1 = randn(n,r);
A2 = randn(m,r);
%
Y1 = X*A1;
A2 = Y1;
Y2 = X'*A2;
A1 = Y2;
Y = X*A1;
L = Y1*inv(A2'*Y1)*Y2';  % compare both svds
svd(X)
svd(L)

It will be included shortly in the Matrix Factorization Jungle but it is also the main tool used in GoDec. The video of  Tianyi Zhou who talks about GoDec and the Bilateral Random Projections can be found here.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.