Literature survey on low rank approximation of matrices

Abstract Low rank approximation of matrices has been well studied in literature. Singular value decomposition, QR decomposition with column pivoting, rank revealing QR factorization, Interpolative decomposition, etc. are classical deterministic algorithms for low rank approximation. But these techniques are very expensive ( operations are required for matrices). There are several randomized algorithms available in the literature which are not so expensive as the classical techniques (but the complexity is not linear in n). So, it is very expensive to construct the low rank approximation of a matrix if the dimension of the matrix is very large. There are alternative techniques like Cross/Skeleton approximation which gives the low-rank approximation with linear complexity in n. In this article we review low rank approximation techniques briefly and give extensive references of many techniques.

• Publication year

  2016

• Venue

  arXiv.org

• Publication date

  2016-06-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/03081087.2016.1267104arXiv 1606.06511
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• Cross/Skeleton approximation is highlighted as an alternative that achieves low-rank approximation with linear complexity in n.

  Confidence 0.95

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• Randomized algorithms are described as cheaper than classical techniques, but their complexity is still not linear in n.

  Confidence 0.87

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• Classical deterministic algorithms for low-rank approximation are presented as expensive for large matrices.

  Confidence 0.88

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review

• classical deterministic algorithms

  method

  Non-random procedures used to compute low-rank matrix approximations in the survey.

  Aliases: deterministic low-rank methods

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• cross/skeleton approximation

  method

  A low-rank approximation approach based on selected rows and columns of a matrix.

  Aliases: cross approximation, skeleton approximation

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• interpolative decomposition

  method

  A matrix approximation that represents a matrix using a subset of its columns or rows.

  Aliases: ID

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• low rank approximation of matrices

  method

  A method for approximating a matrix using another matrix of much smaller rank.

  Aliases: low-rank approximation

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• qr decomposition with column pivoting

  method

  A QR factorization variant that uses column pivoting to help reveal rank structure.

  Aliases: QRCP

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• randomized algorithms

  method

  Algorithms that use randomness to construct low-rank matrix approximations.

  Aliases: randomized low-rank methods

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• rank revealing qr factorization

  method

  A QR-based factorization designed to expose the numerical rank of a matrix.

  Aliases: RRQR

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review
• singular value decomposition

  method

  A matrix factorization used as a classical deterministic tool for low-rank approximation.

  Aliases: SVD

  박진우 (dztg5apj7m) extraction뀨 (7c402c1b98) reviewAK (4715169a40) review--------- ✂ Cut Here ✂ --------- (jqthcshryb) review

• Methods for large scale machine learning

  2016cited by this paper
• Randomized SVDMethods in Hyperspectral Imaging

  2015cited by this paper
• Tensor numerical methods for multidimensional PDES: theoretical analysis and initial applications

  2015cited by this paper
• Low Rank Approximation using Error Correcting Coding Matrices

  2015cited by this paper
• Large-Scale Nyström Kernel Matrix Approximation Using Randomized SVD

  2015cited by this paper
• Lanczos Bidiagonalization for the SVD in SLEPc

  2015cited by this paper
• Frequent Directions: Simple and Deterministic Matrix Sketching

  2015cited by this paper
• Optimal Column Subset Selection by A-Star Search

  2015cited by this paper
• Tighter Low-rank Approximation via Sampling the Leveraged Element

  2014cited by this paper
• Low Rank Matrix Approximation in Linear Time

  2014cited by this paper
• Rank revealing QR factorizations

  2014influential reference
• Low Rank Approximation Lower Bounds in Row-Update Streams

  2014cited by this paper
• A fast block low-rank dense solver with applications to finite-element matrices

  2014cited by this paper
• Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization

  2014cited by this paper
• The Why and How of Nonnegative Matrix Factorization

  2014cited by this paper
• Parallel Implementation of Fast Randomized Algorithms for Low Rank Matrix Decomposition

  2014cited by this paper
• Subspace Iteration Randomization and Singular Value Problems

  2014cited by this paper
• Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds

  2013cited by this paper
• Matrix compression using the Nyström method

  2013cited by this paper
• Distributed Column Subset Selection on MapReduce

  2013cited by this paper
• Matrix Approximation under Local Low-Rank Assumption

  2013cited by this paper
• Greedy column subset selection for large-scale data sets

  2013cited by this paper
• One-shot learning gesture recognition from RGB-D data using bag of features

  2013cited by this paper
• A literature survey of low‐rank tensor approximation techniques

  2013cited by this paper
• Pass-efficient unsupervised feature selection

  2013cited by this paper
• Regularization with randomized SVD for large-scale discrete inverse problems

  2013cited by this paper
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling

  2013cited by this paper
• Relative Errors for Deterministic Low-Rank Matrix Approximations

  2013cited by this paper
• CUR decomposition for compression and compressed sensing of large-scale traffic data

  2013cited by this paper
• Revisiting the Nystrom Method for Improved Large-scale Machine Learning

  2013cited by this paper
• Large scale polyphonic music transcription using randomized matrix decompositions

  2012cited by this paper
• Parallel implementation of a fast randomized algorithm for the decomposition of low rank matrices

  2012cited by this paper
• A note on tensor chain approximation

  2012influential reference
• A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound

  2012cited by this paper
• Hybrid regularization for mri reconstruction with static field inhomogeneity correction

  2012cited by this paper
• Column subset selection via sparse approximation of SVD

  2012cited by this paper
• An Improved Semidiscrete Matrix Decomposition and its Application in Chinese Information Retrieval

  2012cited by this paper
• Randomized SVD Methods in Hyperspectral Imaging

  2012cited by this paper
• A fast algorithm for multiscale electromagnetic problems using interpolative decomposition and multilevel fast multipole algorithm

  2012cited by this paper
• Deterministic CUR for Improved Large-Scale Data Analysis: An Empirical Study

  2012cited by this paper
• Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances

  2012cited by this paper
• Simple and deterministic matrix sketching

  2012cited by this paper
• Applications of Randomized Methods for Decomposing and Simulating from Large Covariance Matrices

  2012cited by this paper
• Machine learning - a probabilistic perspective

  2012cited by this paper
• Probabilistic interpolative decomposition

  2012cited by this paper
• Randomised pseudo-skeleton approximation and its application in electromagnetics

  2011cited by this paper
• Fast low rank approximations of matrices and tensors

  2011cited by this paper
• Numerical Linear Algebra

  2011cited by this paper
• Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm

  2011cited by this paper
• Randomized Algorithms for Low-Rank Matrix Decomposition

  2011cited by this paper
• Matrix Computations

  2011influential reference
• Sublinear Randomized Algorithms for Skeleton Decompositions

  2011cited by this paper
• Optimal column-based low-rank matrix reconstruction

  2011cited by this paper
• O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

  2011cited by this paper
• Adaptive Cross Approximation of Multivariate Functions

  2011cited by this paper
• Near Optimal Column-Based Matrix Reconstruction

  2011cited by this paper
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate

  2011influential reference
• Fast Nonnegative Matrix Factorization: An Active-Set-Like Method and Comparisons

  2011cited by this paper
• On Tensors, Sparsity, and Nonnegative Factorizations

  2011cited by this paper
• Error estimates for two-dimensional cross approximation

  2010influential reference
• Very Large-scale Low-rank Approximation

  2010cited by this paper
• Efficient Volume Sampling for Row/Column Subset Selection

  2010cited by this paper
• Generalizing the column–row matrix decomposition to multi-way arrays

  2010cited by this paper
• Making Large-Scale Nyström Approximation Possible

  2010cited by this paper
• How to find a good submatrix

  2010influential reference
• Matrix Coherence and the Nystrom Method

  2010cited by this paper
• TT-cross approximation for multidimensional arrays

  2010cited by this paper
• Subset Selection Algorithms: Randomized vs. Deterministic

  2010cited by this paper
• Column subset selection for approximating data matrices

  2009cited by this paper
• EFFICIENT ALGORITHMS FOR SPARSE SINGULAR VALUE DECOMPOSITION

  2009cited by this paper
• Nonnegative Matrix and Tensor Factorizations - Applications to Exploratory Multi-way Data Analysis and Blind Source Separation

  2009cited by this paper
• A fast and efficient algorithm for low-rank approximation of a matrix

  2009cited by this paper
• CUR matrix decompositions for improved data analysis

  2009cited by this paper
• Spectral Algorithms

  2009cited by this paper
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

  2009influential reference
• Numerical linear algebra in the streaming model

  2009cited by this paper
• Fast Electromagnetic Solvers for Large-Scale Naval Scattering Problems

  2008cited by this paper
• Verification of the cross 3D algorithm on quantum chemistry data

  2008cited by this paper
• The Adaptive Cross Approximation Algorithm Applied to Electromagnetic Scattering by Bodies of Revolution

  2008cited by this paper
• Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

  2008cited by this paper
• An improved approximation algorithm for the column subset selection problem

  2008cited by this paper
• Improved Nyström low-rank approximation and error analysis

  2008cited by this paper
• A Randomized Algorithm for Principal Component Analysis

  2008cited by this paper
• Regularized Alternating Least Squares Algorithms for Non-negative Matrix/Tensor Factorization

  2007cited by this paper
• A robust and efficient parallel SVD solver based on restarted Lanczos bidiagonalization.

  2007cited by this paper
• Randomized algorithms for the low-rank approximation of matrices

  2007cited by this paper
• Algorithm XXX: Computation and Uses of the Semidiscrete Matrix Decomposition

  2007cited by this paper
• Relative-Error CUR Matrix Decompositions

  2007cited by this paper
• A fast randomized algorithm for the approximation of matrices ✩

  2007cited by this paper
• The Fast Solution of Boundary Integral Equations

  2007cited by this paper
• Projected Gradient Methods for Nonnegative Matrix Factorization

  2007cited by this paper
• Algorithms and applications for approximate nonnegative matrix factorization

  2007cited by this paper
• Understanding Complex Datasets: Data Mining with Matrix Decompositions

  2007cited by this paper
• Fast computation of low-rank matrix approximations

  2007cited by this paper
• Matrix approximation and projective clustering via volume sampling

  2006cited by this paper
• Adaptive Sampling and Fast Low-Rank Matrix Approximation

  2006cited by this paper
• Improved Approximation Algorithms for Large Matrices via Random Projections

  2006cited by this paper
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

  2006cited by this paper
• Parallel Algorithms for the Singular Value Decomposition

  2005cited by this paper
• On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning

  2005cited by this paper

• Approximate anchor-based similarity graph and its applications for large-scale data

  2026cites this paper
• Federated Split Learning via Low-Rank Approximation: A Communication-Efficient Approach

  2026cites this paper
• Comparison of Input-Data Matrix Representations Used for Continual Learning with Orthogonal Weight Modification on Edge Devices

  2026cites this paper
• A study and formal framework of the composability of LLM compression techniques

  2026cites this paper
• A Benchmark Study of Neural Network Compression Methods for Hyperspectral Image Classification

  2026cites this paper
• Communication-Efficient Federated Learning by Exploiting Spatio-Temporal Correlations of Gradients

  2026cites this paper
• Large Language Model Compression via the Nested Activation-Aware Decomposition

  2025cites this paper
• Efficient Fine-tuning of Large Language Models Based on Parameter-efficient LoRA Techniques

  2025cites this paper
• Bayesian Kernel Machine Regression via Random Fourier Features for Estimating Joint Health Effects of Multiple Exposures

  2025cites this paper
• Fast LDL factorization for dense and sparse symmetric matrices over an arbitrary field

  2025cites this paper
• Non-Negative Matrix Factorization in Recommender Models: Concept, Survey, and Future Direction

  2025cites this paper
• Smooth Model Compression without Fine-Tuning

  2025cites this paper
• Error Estimates for the Arnoldi Approximation of a Matrix Square Root

  2025cites this paper
• DPQ-HD: Post-Training Compression for Ultra-Low Power Hyperdimensional Computing

  2025cites this paper
• Clustering-Based Low-Rank Matrix Approximation for Medical Image Compression

  2025cites this paper
• Mixed Precision Iterative Refinement for Low-Rank Matrix and Tensor Approximations

  2025cites this paper
• Multi-class classification framework for ear imaging using attention-based hybrid dense CNN and non-linear manifold approximation

  2025cites this paper
• Lightweight deep learning models for aerial scene classification: A comprehensive survey

  2025cites this paper
• RIS-Aided NLoS Monostatic Multi-Target Sensing Under Angle-Doppler Coupling

  2025cites this paper
• Improving Deep Random Vector Functional Link Networks through computational optimization of regularization parameters

  2025cites this paper
• Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling

  2025cites this paper
• UPPR+: Scaling Uncertain Personalised PageRank Computation on Billion-Sized Graphs with Mutually Exclusive Edges

  2025cites this paper
• A deep adaptive bidirectional generative adversarial neural network (Bi-GAN) for groundwater contamination source estimation

  2025cites this paper
• Interplay between Bayesian neural networks and deep learning: A survey

  2025cites this paper
• Tessellated Distributed Computing

  2025cites this paper
• Clustering-based Low-Rank Matrix Approximation: An Adaptive Theoretical Analysis with Application to Data Compression

  2025cites this paper
• Survey of neural network optimization methods for sustainable AI: From data preprocessing to hardware acceleration

  2025cites this paper
• Research and Engineering Practice of Var-Voltage Control in Primary and Distribution Networks Considering the Reactive Power Regulation Capability of Distributed PV Systems

  2025cites this paper
• A systematic review of low-rank and local low-rank matrix approximation in big data medical imaging

  2025cites this paper
• A Low-Rank Matrix Approach to Compute Polynomial Approximations of Smooth Two-Dimensional Functions

  2024cites this paper
• Africa, ChatGPT, and Generative AI Systems: Ethical Benefits, Concerns, and the Need for Governance

  2024cites this paper
• Quantum generalized least squares method in system identification

  2024influential citation
• Personalized Multimedia Recommendation Systems Using Higher-Order Tensor Singular-Value-Decomposition

  2024cites this paper
• Real-time Adaptive and Localized Spatiotemporal Clutter Filtering for Ultrasound Small Vessel Imaging

  2024cites this paper
• A Decoupled Channel Estimation Method for Beyond Diagonal RIS

  2024cites this paper
• Non-iterative model-based inversion for low channel-count optical ultrasound imaging

  2024cites this paper
• Low-rank Representation for Seismic Reflectivity and its Applications in Least-squares Imaging

  2024cites this paper
• The Space Complexity of Approximating Logistic Loss

  2024cites this paper
• Learning Embedding Representations in High Dimensions

  2024cites this paper
• LLM Inference Unveiled: Survey and Roofline Model Insights

  2024cites this paper
• Checking the Sufficiently Scattered Condition Using a Global Non-Convex Optimization Software

  2024cites this paper
• Efficient Blind Hyperspectral Unmixing Framework Based on CUR Decomposition (CUR-HU)

  2024cites this paper
• Efficient solution of ill-posed integral equations through averaging

  2024cites this paper
• Sparse subnetwork inference for neural network epistemic uncertainty estimation with improved Hessian approximation

  2024cites this paper
• Integrated Communications and Localization for Massive MIMO LEO Satellite Systems

  2024cites this paper
• Ef-QuantFace: Streamlined Face Recognition with Small Data and Low-Bit Precision

  2024cites this paper
• Task-based low-rank hybrid parallel Cholesky factorization for distributed memory environment

  2024cites this paper
• EdgeNet: a low-power image recognition model based on small sample information

  2024cites this paper
• Channel Estimation for Beyond Diagonal RIS via Tensor Decomposition

  2024cites this paper
• Enhancing deep stochastic configuration networks: Efficient training via low-rank matrix approximation

  2024cites this paper
• Improved xDeepFM With Single Value Decomposition and Attention Mechanism

  2024cites this paper
• Cross-extrapolation reconstruction of low-rank functions and application to quantum many-body observables in the strong coupling regime

  2024cites this paper
• Low-rank rotation matrices-based DOA estimation with a moored circular vector sensor array

  2024cites this paper
• Efficient quantum state estimation with low-rank matrix completion

  2024cites this paper
• Model-Driven Compressive Spherical Array Sampling of Antenna Near Field Using Accelerated Pseudoskeleton Tensor Approximation

  2024influential citation
• Subspace learning for feature selection via rank revealing QR factorization: Fast feature selection

  2024cites this paper
• Generalized Policy Iteration using Tensor Approximation for Hybrid Control

  2024cites this paper
• Efficient and Accurate PageRank Approximation on Large Graphs

  2024cites this paper
• Knowledge Translation: A New Pathway for Model Compression

  2024cites this paper
• Why do small language models underperform? Studying Language Model Saturation via the Softmax Bottleneck

  2024cites this paper
• fg-ORKA: fast and gridless reconstruction of moving and deforming objects in multidimensional data

  2024cites this paper
• Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions

  2024cites this paper
• QR-PULP: Streamlining QR Decomposition for RISC-V Parallel Ultra-Low-Power Platforms

  2024cites this paper
• Low-Complexity Joint Active and Passive Beamforming Design for IRS-Assisted MIMO

  2023cites this paper
• Towards explainability of hashtags in the light of Graph Spectral Clustering methods

  2023cites this paper
• A motion assessment method for reference stack selection in fetal brain MRI reconstruction based on tensor rank approximation

  2023cites this paper
• Current and future role of data fusion and machine learning in infrastructure health monitoring

  2023cites this paper
• Higher-Order Tensor-Based Joint Transmit/Receive Beamforming and IRS Optimization

  2023cites this paper
• Statistica Sinica

  2023cites this paper
• Generalized uncertainty in surrogate models for concrete strength prediction

  2023cites this paper
• Factor Fitting, Rank Allocation, and Partitioning in Multilevel Low Rank Matrices

  2023cites this paper
• Estimation of embedding vectors in high dimensions

  2023cites this paper
• Kriging, Polynomial Chaos Expansion, and Low-Rank Approximations in Material Science and Big Data Analytics

  2023cites this paper
• Neural Language Model Pruning for Automatic Speech Recognition

  2023cites this paper
• Seq-SVF: An unsupervised data-driven method for automatically identifying hidden governing equations

  2023cites this paper
• Novel Personalized Multimedia Recommendation Systems Using Tensor Singular-Value-Decomposition

  2023cites this paper
• Low-Dimensional Space Modeling-Based Differential Evolution for Large-Scale Global Optimization Problems

  2023influential citation
• Feature Space Sketching for Logistic Regression

  2023cites this paper
• Generalized Matrix Local Low Rank Representation by Random Projection and Submatrix Propagation

  2023cites this paper
• Communication Efficient Federated Learning With Heterogeneous Structured Client Models

  2023cites this paper
• Maximal volume matrix cross approximation for image compression and least squares solution

  2023cites this paper
• Memory Efficient Kernel Approximation for Non-Stationary and Indefinite Kernels

  2022cites this paper
• A Unified Framework for Optimization-Based Graph Coarsening

  2022cites this paper
• A new kernel regression approach for robustified L2 boosting

  2022cites this paper
• Decay estimate of bivariate Chebyshev coefficients for functions with limited smoothness

  2022cites this paper
• Nebula-I: A General Framework for Collaboratively Training Deep Learning Models on Low-Bandwidth Cloud Clusters

  2022cites this paper
• Unsupervised feature selection method based on iterative similarity graph factorization and clustering by modularity

  2022cites this paper
• A strategy to estimate the optimal low-rank in incremental SVD-based algorithms for recommender systems

  2022influential citation
• Task-parallel tiled direct solver for dense symmetric indefinite systems

  2022cites this paper
• CMD: controllable matrix decomposition with global optimization for deep neural network compression

  2022cites this paper
• Arithmetic circuit tensor networks, multivariable function representation, and high-dimensional integration

  2022cites this paper
• Learning Feynman Diagrams with Tensor Trains

  2022cites this paper
• Feature distillation Siamese networks for object tracking

  2022cites this paper
• A fault diagnosis method for electric vehicle power lithium battery based on wavelet packet decomposition

  2022cites this paper
• Two accelerated isogeometric boundary element method formulations: fast multipole method and hierarchical matrices method

  2022cites this paper
• Tensor train for global optimization problems in robotics

  2022cites this paper
• Inexact penalty decomposition methods for optimization problems with geometric constraints

  2022cites this paper
• Polynomial whitening for high-dimensional data

  2022cites this paper
• Revisiting Memory Efficient Kernel Approximation: An Indefinite Learning Perspective

  2021cites this paper
• The Kolmogorov Superposition Theorem can Break the Curse of Dimensionality When Approximating High Dimensional Functions

  2021cites this paper