No Access

On Low Rank Approximation of Linear Operators in $p$ -Norms and Some Algorithms

Yang Liu

Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA

https://doi.org/10.1142/S0217595916500238Cited by:0 (Source: Crossref)

Abstract

In this paper, we study the optimal or best approximation of any linear operator by low rank linear operators, especially, any linear operator on the $ℓ_{p}$ -space, $p \in [1, \infty)$ , under $ℓ_{p}$ norm, or in Minkowski distance. Considering generalized singular values and using techniques from differential geometry, we extend the classical Schmidt–Mirsky theorem in the direction of the $ℓ_{p}$ -norm of linear operators for some $p$ values. Also, we develop and provide algorithms for finding the solution to the low rank approximation problems in some nontrivial scenarios. The results can be applied to, in particular, matrix completion and sparse matrix recovery.

Keywords:

References

Bhaskara, A and A Vijayaraghavan (2011). Approximating matrix $p$ -norms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 497–511. Google Scholar
Cai, JF, EJ Candès and Z Shen (2010). A singular, value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4), 1956–1982. Crossref, Web of Science, Google Scholar
Candès, EJ and B Recht (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772. Crossref, Web of Science, Google Scholar
Candes, EJ and T Tao (2005). Decoding by linear programming. IEEE Transactions on Information Theory, 51(12), 4203–4215. Crossref, Web of Science, Google Scholar
Friedland, S and A Torokhti (2007). Generalized rank-constrained matrix approximations. SIAM Journal on Matrix Analysis and Applications, 29, 656–659. Crossref, Web of Science, Google Scholar
Gärtner, B and J Matousek (2012). Approximation Algorithms and Semidefinite Programming. Springer. Crossref, Google Scholar
Goodner, DB (1950). Projections in normed linear spaces. Transactions of the American Mathematical Society, 69(89), 108. Google Scholar
Hendrickx, JM and A Olshevsky (2010). Matrix $p$ -norms are np-hard to approximate if $p \neq 1, 2, \infty$ . SIAM Journal on Matrix Analysis and Applications, 31, 2802–2812. Crossref, Web of Science, Google Scholar
Higham, NJ (2013). Estimating the matrix $p$ -norm. Numerische Mathematik, 62(1), 539–555. Crossref, Web of Science, Google Scholar
Hillar, CJ and LH Lim (2013). Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6), 45. Crossref, Web of Science, Google Scholar
Johnson, WB and J Lindenstrauss (2003). Handbook of the Geometry of Banach Spaces, Vol. 2. North Holland. Google Scholar
Kelley, JL (1952). Banach spaces with the extension property. Transactions of the American Mathematical Society, 72, 323–326. Crossref, Web of Science, Google Scholar
Lai, MJ and Y Liu (2016). The null space property for sparse recovery from multiple measurement vectors. Applied and Computational Harmonic Analysis, 30(3), 402–406. Crossref, Web of Science, Google Scholar
Lai, MJ and Y Liu (2015). The probabilistic estimates on the largest and smallest $q$ -singular values of random matrices. Mathematics of Computation, 84(294), 1775–1794. Crossref, Web of Science, Google Scholar
Lee, J (2010). Introduction to Topological Manifolds, Vol. 940. Springer Science & Business Media. Google Scholar
Liberty, E, F Woolfe, PG Martinsson, V Rokhlin and M Tygert (2007). Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences, 104(51), 20167. Crossref, Web of Science, Google Scholar
Liu, Y, T Mi and S Li (2012). Compressed sensing with general frames via optimal-dual-based-analysis. IEEE Transactions on Information Theory, 58(7), 4201–4214. Crossref, Web of Science, Google Scholar
Milnor, JW and JD Stasheff (1974). Characteristic Classes. Number 76. Princeton University Press. Crossref, Google Scholar
Nachbin, L (1950). A theorem of the hahn-banach type for linear transformations. Transactions of the American Mathematical Society, 68(1), 28–46. Crossref, Google Scholar
Pietsch, A (2007). History of Banach Spaces and Linear Operators. Birkhauser. Google Scholar
Steinberg, D (2005). Computation of matrix norms with applications to robust optimization. Master’s thesis, Technion-Israel Institute of Technology. Google Scholar
Woolfe, F, E Liberty, V Rokhlin and M Tygert (2008). A fast randomized algorithm for the approximation of matrices. Applied and Computational Harmonic Analysis, 25(3), 335–366. Crossref, Web of Science, Google Scholar
Zhang, X, Y Yu, M White, R Huang and D Schuurmans (2011). Convex sparse coding, subspace learning, and semi-supervised extensions. In AAAI. Google Scholar