Precise expressions for random projections: Low-rank approximation and randomized Newton
It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case performance of sketching, existing guarantees are typically very different from what is observed in practice. We exploit recent developments in the spectral analysis of random matrices to develop novel techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks, ranging from low-rank approximation to iterative stochastic optimization. Our results apply to several popular sketching methods, including Gaussian and Rademacher sketches, and they enable precise analysis of these methods in terms of spectral properties of the data. Empirical results show that the expressions we derive reflect the practical performance of these sketching methods, down to lower-order effects and even constant factors.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionStochastic OptimizationSimilar Papers 제목 키워드 기반
Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions
Random sampling is a fundamental tool in modern machine learning and numerical linear algebra for reducing the computational cost of large-scale matrix problems. Existing analyses, however, rely primarily on subspace emb…
Node Similarities under Random Projections: Limits and Pathological Cases
Random Projections have been widely used to generate embeddings for various graph learning tasks due to their computational efficiency. The majority of applications have been justified through the Johnson-Lindenstrauss L…
Computational EfficiencyGraph LearningLEMMAPartially adaptive filtering using randomized projections
This short note addresses the design of a partially adaptive filter to retrieve a signal of interest in the presence of strong low-rank interference and thermal noise. We consider a generalized sidelobe canceler implemen…
Constrained low-tubal-rank tensor recovery for hyperspectral images mixed noise removal by bilateral random projections
In this paper, we propose a novel low-tubal-rank tensor recovery model, which directly constrains the tubal rank prior for effectively removing the mixed Gaussian and sparse noise in hyperspectral images. The constraints…
DenoisingHyperspectral Image DenoisingImage DenoisingInput Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling
We present a new algorithm for finding a near optimal low-rank approximation of a matrix $A$ in $O(nnz(A))$ time. Our method is based on a recursive sampling scheme for computing a representative subset of $A$'s columns,…