Matrices with displacement structure such as Pick, Vandermonde, and Hankel
matrices appear in a diverse range of applications. In this paper, we use an
extremal problem involving rational functions to derive explicit bounds on the
singular values of such matrices. For example, we show that the $k$th singular
value of a real $n\times n$ positive definite Hankel matrix, $H_n$, is bounded
by $C\rho^{-k/\log n}\|H\|_2$ with explicitly given constants $C>0$ and
$\rho>1$, where $\|H_n\|_2$ is the spectral norm. This means that a real
$n\times n$ positive definite Hankel matrix can be approximated, up to an
accuracy of $\epsilon\|H_n\|_2$ with $0<\epsilon<1$, by a rank
$\mathcal{O}(\log n\log(1/\epsilon) )$ matrix. Analogous results are obtained
for Pick, Cauchy, real Vandermonde, L\"{o}wner, and certain Krylov matrices.

本文探讨了带有位移结构（如 Pick 矩阵、Vandermonde 矩阵和 Hankel 矩阵）的矩阵，并利用极值问题得出了这些矩阵奇异值的显式界限，从而可以通过秩近似来逼近这些矩阵

关于具有位移结构的矩阵的奇异值

On the singular values of matrices with displacement structure

$\newcommand{\MatA}{\mathcal{M}}$ $\newcommand{\eps}{\varepsilon}$
$\newcommand{\NSize}{\mathsf{N}{}}$ $\newcommand{\MatB}{\mathcal{B}}$
$\newcommand{\Fnorm}[1]{\left\| {#1} \right\|_F}$
$\newcommand{\PrcOpt}[2]{\mu_{\mathrm{opt}}\pth{#1, #2}}$
$\newcommand{\pth}[1]{\left(#1\right)}$
Given a matrix $\MatA$ with $n$ rows and $d$ columns, and fixed $k$ and
$\eps$, we present an algorithm that in linear time (i.e., $O(\NSize )$)
computes a $k$-rank matrix $\MatB$ with approximation error $\Fnorm{\MatA -
\MatB}^2 \leq (1+\eps) \PrcOpt{\MatA}{k}$, where $\NSize = n d$ is the input
size, and $\PrcOpt{\MatA}{k}$ is the minimum error of a $k$-rank approximation
to $\MatA$.
This algorithm succeeds with constant probability, and to our knowledge it is
the first linear-time algorithm to achieve multiplicative approximation.

给定一个矩阵，提出了一个线性时间复杂度算法计算其 k 秩矩阵，达到了乘性近似，误差满足 (1+ϵ) 最小误差。