Best low-rank approximations and Kolmogorov n-width

Espen Sande (EPFL)

Abstract: It is well known that if the singular values of a matrix A are distinct, then the best rank-n approximation to A is uniquely determined in the Frobenius norm and given by the truncated singular value decomposition. On the other hand, this uniqueness is in general not true for best rank-n approximations in the spectral norm. In this talk we relate the problem of finding best rank-n approximations in the spectral norm to Kolmogorov n-widths and corresponding optimal spaces. By providing new criteria for optimality of subspaces with respect to the n-width, we describe a large family of best rank-n approximations to A. This results in a variety of solutions to the best low-rank approximation problem and provides alternatives to the truncated singular value decomposition. This variety can be exploited to obtain best low-rank approximations with problem-oriented properties. Special attention is paid to the case of rank-1 approximation.
We further discuss the generalization of these results to compact operators in L^2, and explain how they can be used to describe the out-performance of smooth spline approximations of differential equations (so-called k-refinement in isogeometric analysis) when compared to classical finite element methods.
This talk is based on joint work with Michael S. Floater, Carla Manni and Hendrik Speleers.