Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time

DOI10.1007/S00453-019-00642-0zbMath1432.68564OpenAlexW2981456157MaRDI QIDQ2309471

Kohei Hayashi, Yuichi Yoshida

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00642-0

zbMATH Keywords

VC dimensionproperty testingconstant-time algorithmsubspace proximity problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational aspects of data analysis and big data (68T09)

Uses Software

• ROBPCA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Density estimation in the \(L^ \infty\) norm for dependent data with applications to the Gibbs sampler
• Note on Jordan elimination, linear programming and Tchebyscheff approximation
• \(\epsilon\)-nets and simplex range queries
• The historical development of the linear minimax absolute residual estimation procedure 1786--1960
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Multidimensional scaling. I: Theory and method
• Graph limits and parameter testing
• Powers of tensors and fast matrix multiplication
• Algorithm 495: Solution of an Overdetermined System of Linear Equations in the Chebychev Norm [F4]
• Computing the Exact Least Median of Squares Estimate and Stability Diagnostics in Multiple Linear Regression
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Testing of Clustering
• Gowers Norm, Function Limits, and Parameter Estimation
• Local Testing for Membership in Lattices
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing Matrix Rank, Optimally
• A characterization of locally testable affine-invariant properties via decomposition theorems
• Learning the parts of objects by non-negative matrix factorization
• On the Maximum Deviation of the Sample Density
• Norms for Smoothing and Estimation
• Property testing in bounded degree graphs

This page was built for publication: Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time