  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^TA_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.
