Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution
We study the classic matrix cross approximation based on the maximal volume submatrices. Our main results consist of an improvement of the classic estimate for matrix cross approximation and a greedy approach for finding the maximal volume submatrices. More precisely, we present a new proof of the classic estimate of the inequality with an improved constant. Also, we present a family of greedy maximal volume algorithms to improve the computational efficiency of matrix cross approximation. The proposed algorithms are shown to have theoretical guarantees of convergence. Finally, we present two applications: image compression and the least squares approximation of continuous functions. Our numerical results at the end of the paper demonstrate the effective performance of our approach.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyImage CompressionSimilar Papers 제목 키워드 기반
piCholesky: Polynomial Interpolation of Multiple Cholesky Factors for Efficient Approximate Cross-Validation
The dominant cost in solving least-square problems using Newton's method is often that of factorizing the Hessian matrix over multiple values of the regularization parameter ($\lambda$). We propose an efficient way to in…
Minimizing the Maximal Rank
In computer vision, many problems can be formulated as finding a low rank approximation of a given measurement matrix. Ideally, if all elements of the measurement matrix are available, this is easily solved in the L2-nor…
DenoisingJoint Deformable Registration of Large EM Image Volumes: A Matrix Solver Approach
Large electron microscopy image datasets for connectomics are typically composed of thousands to millions of partially overlapping two-dimensional images (tiles), which must be registered into a coherent volume prior to …
Image RegistrationLow-Rank Matrix Factorizations with Volume-based Constraints and Regularizations
Low-rank matrix factorizations are a class of linear models widely used in various fields such as machine learning, signal processing, and data analysis. These models approximate a matrix as the product of two smaller ma…
blind source separationImputationSpherical sampling methods for the calculation of metamer mismatch volumes
In this paper, we propose two methods of calculating theoretically maximal metamer mismatch volumes. Unlike prior art techniques, our methods do not make any assumptions on the shape of spectra on the boundary of the mis…