2011/12/22 by Tianyi Zhou, Dacheng Tao, Zhou, Tianyi +1
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical and numerical algorithms #cs.DS #stat.ML
paper · pdf · doi:10.48550/arxiv.1112.5215
17 pages, 3 figures, technical report
arxiv created 2011/12/22 · openalex publication_date 2011/12/22 · arxiv updated 2011/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Y1=XA1 and Y2=XTA2, 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.