5 May 2017 Characterizing L1-norm best-fit subspaces
Author Affiliations +
Fitting affine objects to data is the basis of many tools and methodologies in statistics, machine learning, and signal processing. The L1 norm is often employed to produce subspaces exhibiting a robustness to outliers and faulty observations. The L1-norm best-fit subspace problem is directly formulated as a nonlinear, nonconvex, and nondifferentiable optimization problem. The case when the subspace is a hyperplane can be solved to global optimality efficiently by solving a series of linear programs. The problem of finding the best-fit line has recently been shown to be NP-hard. We present necessary conditions for optimality for the best-fit subspace problem, and use them to characterize properties of optimal solutions.
Conference Presentation
© (2017) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
J. Paul Brooks, José H. Dulá, "Characterizing L1-norm best-fit subspaces", Proc. SPIE 10211, Compressive Sensing VI: From Diverse Modalities to Big Data Analytics, 1021103 (5 May 2017); doi: 10.1117/12.2263690; https://doi.org/10.1117/12.2263690


Group sparse optimization by alternating direction method
Proceedings of SPIE (September 26 2013)
Robust decomposition of 3-way tensors based on L1-norm
Proceedings of SPIE (May 14 2018)
Optimality in the design of overcomplete decompositions
Proceedings of SPIE (September 04 2009)
Approximate Karhunen-Loeve transform for image processing
Proceedings of SPIE (March 13 1996)
Signal Processing Computational Needs
Proceedings of SPIE (April 04 1986)
Exact and approximate time-shift operators
Proceedings of SPIE (April 28 2009)

Back to Top