0000-0002-1398-0699

0000-0003-0865-9021

0000-0003-2288-038X

Andrew Mao et al

Andrew Mao.

National Institutes of Health Grant Numbers: F30 AG077794, T32 GM136573, P41
EB017183

# Unbiased Neural Networks for Parameter Estimation in Quantitative MRI

Andrew Mao  Sebastian Flassbeck  Jakob Assländer  Center for Biomedical
Imaging, Department of Radiology, New York University Grossman School of
Medicine, New York, New York  Center for Advanced Imaging Innovation and
Research (CAI2R), Department of Radiology, New York University Grossman School
of Medicine, New York, New York  Vilcek Institute of Graduate Biomedical
Sciences, New York University Grossman School of Medicine, New York, New York
<EMAIL_ADDRESS>
###### keywords:

quantitative MRI, neural networks, Cramér-Rao bound, parameter estimation

††articletype: PRE-PRINT – SUBMITTED TO MAGNETIC RESONANCE IN MEDICINE


# A Note on Error Bounds for Pseudo Skeleton Approximations of Matrices

Frank de Hoog
Data 61
CSIRO
Black Mountain, ACT 2601
<EMAIL_ADDRESS>
&Markus Hegland
Mathematical Sciences Institute
Australian National University
Acton, ACT 2601
<EMAIL_ADDRESS>
###### Abstract

A new and improved bound for the Chebyshev norm of the error of a maximal
volume pseudo-skeleton matrix approximation is presented. This bound uses all
the singular values of the approximated matrix up to the $r+1$st where $r$ is
the rank of the approximation. It is shown that this bound is in particular
useful for the case of matrices with slowly decaying singular values where the
approximation rank is of moderate size. In this case the original bounds for
the maximal volume approximation are of the form $(r+1)\sigma_{r+1}$ and thus
are very large and if $\sigma_{r+1}=O(1/(r+1))$ do not even indicate
convergence.

A new approximation based on the truncated singular value decomposition of a
maximal volume approximation is analysed. It is demonstrated that this
approximation is in some cases asymptotically as a good as the truncated
singular value approximation of the original matrix. This new approximation is
shown to have similar approximation properties as the maximal $r$-volume
method analysed by Osinsky and Zamarashkin [Linear Algebra and its
Applications 537 (2018), 221–249] for the case of symmetric positive definite
matrices.

##  1 Introduction

A large matrix $M\in\mathbb{R}^{m\times n}$ can be well approximated by a
matrix of rank $r$ if the singular values $\sigma_{k}$ of $M$ decay rapidly or
if $M$ has a low effective dimension [9]. A natural approximation $M_{r}$ uses
the _truncated singular value decomposition of $M$_ which is obtained from the
singular value decomposition of $M$ by replacing the nonzero singular values
$\sigma_{r+1},\ldots,\sigma_{\operatorname{rank}(M)}$ of $M$ by zero. It is
assumed that the singular values are ordered by decreasing size. A challenge
of using this approximation in practice are the high computational costs and
the difficulty in interpreting the spaces spanned by the first $r$ singular
vectors in terms of the columns and rows of $M$, respectively.

The approximation $M_{r}$ has be shown to be optimal in the Schatten norms
(which includes the Frobenius and spectral norms, see Eckart-Young-Mirski
theorem [1]). We will denote the spectral norm of a matrix $M$ by $\lVert
M\rVert_{2}$ and the error bound is an equality

$\lVert M_{r}-M\rVert_{2}=\sigma_{r+1}.$

Here we are interested in how well the matrix elements are approximated and
thus use the Chebyshev norm defined by

$\|M\|_{C}=\max_{i,j}|M_{i,j}|.$

It follows from this definition of the Chebyshev norm and the characterisation
of the spectral norm as the maximal value of $(u,Mv)$ over all $u,v$ with
$\lVert u\rVert=\lVert v\rVert=1$ that $\lVert M\rVert_{C}\leq\lVert
M\rVert_{2}$ and thus

$\lVert M_{r}-M\rVert_{C}\leq\sigma_{r+1}.$

This bound is tight and it is an equality for diagonal matrices. The simple
example

$M=\frac{1}{2}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}\begin{bmatrix}\sigma_{1}&0\\\
0&\sigma_{2}\end{bmatrix}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}$

satisfies $\lVert M_{1}-M\rVert_{C}=\sigma_{2}/2$ so the bound using the
spectral norm $\lVert M_{1}-M\rVert_{2}=\sigma_{2}$ substantially
overestimates the Chebyshev norm of the error.

The _pseudo skeleton or CUR approximation_ defined below often leads methods
which are computationally efficient and accurate.

######  Definition 1 (Pseudo skeleton approximation).

Let $M\in\mathbb{R}^{m,n}$ be a real matrix satisfying

$P_{1}MP_{2}^{T}=\begin{bmatrix}A&B\\\ C&D\end{bmatrix}$

for some permutation matrices $P_{1}\in\mathbb{R}^{m,m}$ and
$P_{2}\in\mathbb{R}^{n,n}$ and $A\in\mathbb{R}^{p,q}$. Furthermore, let
$A^{+}$ be the generalised (Moore-Penrose) inverse of $A$. Then

  * •

the matrix

$\widehat{M}=P_{1}^{T}\begin{bmatrix}A\\\
C\end{bmatrix}A^{+}\begin{bmatrix}A&B\end{bmatrix}P_{2}$

is called a _pseudo skeleton (or CUR) approximation of $M$_ and

  * •

the resulting approximation is called a _maximal volume approximation_ if the
permutations $P_{1}$ and $P_{2}$ are chosen such that

    * –

$\operatorname{rank}(A)=r$ is maximal

    * –

the $r$-volume $\operatorname{vol}_{r}(A)=\sigma_{1}\cdots\sigma_{r}$ is
maximal.

We will assume $p\leq q$ in the following sections and let $\widehat{M}$
always be the maximal volume pseudo skeleton approximation of
$M\in\mathbb{R}^{n,m}$ with parameters $p,q$. Furthermore we will assume that
$M$ has been reordered such that

$M=\begin{bmatrix}A&B\\\ C&D\end{bmatrix}$

where $A$ has both maximal rank $r$ and maximal $r$-volume. Thus the
permutations $P_{i}$ in Definition 1 are identities.

One can show that

$r\leq p\leq q$

and

$\operatorname{rank}(\widehat{M})=r.$

It follows directly from the Definition 1 that if $r<p$ then
$\operatorname{rank}(M)=r$ and one can show that in this case

$\lVert\widehat{M}-M\rVert_{C}=0.$

When we are thus proving error bounds for maximal volume skeleton
approximations we only need to consider the case $r=p$. We will, however,
formulate the bounds in terms of $r=\operatorname{rank}(A)$ as this is equal
to the rank of the approximation.

The following theorem has been shown by Goreinov and Tyrtyshnikov in [2].

######  Theorem 1 (Goreinov-Tyrtyshnikov[2]).

Let $\widehat{M}$ be a maximal volume pseudo skeleton approximation of $M$
parameters $p=q$ and let $r=\operatorname{rank}{(\widehat{M})}$. Then

$\|\widehat{M}-M\|_{C}\leq\left(r+1\right)\sigma_{r+1}\left(M\right).$

This bound suggests that the error of any CUR approximation may be
substantially larger than error of the approximation based on the truncated
singular value decomposition. An approximation proposed by Osinsky and
Zamarashkin in [7] gives substantially better errors in many cases. They
propose a larger $A$ and replace the generalised inverse $A^{+}$ in the
pseudo-skeleton approximation by the generalised inverse $A_{r}^{+}$ where
$A_{r}$ is the rank $r$ approximation of the matrix $A$ based on the truncated
singular value decomposition. We denote this _rank $r$ pseudo-skeleton
approximation_ by $\widetilde{M}_{r}$. Instead of the maximal volume of $A$
one then chooses the permutations to maximise the volume of $A_{r}$ which is
also called the _$r$ -projective volume of $A$_. The error of the resulting
approximation $\widetilde{M}_{r}$ has then been shown to be bounded by:

######  Theorem 2 (Osinsky-Zamarashkin[7]).

Let $\widetilde{M}_{r}$ be the rank $r$ pseudo skeleton approximation with
maximal $r$-projective volume where the parameters $p,q$ are defined above and
larger or equal to $r$. Then

$\left\|M-\widetilde{M}_{r}\right\|_{C}\
\leq\sqrt{\left(1+\frac{r}{p-r+1}\right)\left(1+\frac{r}{q-r+1}\right)}\;\sigma_{r+1}(M)$
(1)

One can see that if $p$ and $q$ are chosen sufficiently large, the error bound
obtained in Theorem 2 for the rank $r$ pseudo skeleton approximation by
Osinsky and Zamarashkin is close to the singular value $\sigma_{r+1}(M)$. For
the case $p=q=2r-1$ the bound obtained is twice $\sigma_{r+1}(M)$.

In many cases, however, the upper bound given in Theorem 1 substantially
overestimates the actual error of the original maximal volume pseudo-skeleton
approximation. In fact, it can be seen that the error depends on the spectral
decay. Better upper bounds for the pseudo skeleton approximation have been
obtained in [5] in the context of nuclear norms. In practice this does not
matter so much for fast decaying singular values where one typically utilises
small ranks $r$ and the factor $r+1$ does not have a major impact on the
error. This is different for slowly decaying singular values. For example, if
$\sigma_{k}=1/k$ the error bound of Theorem 1 would suggest that the pseudo-
skeleton approximation does not converge as $r\rightarrow\infty$ at all. Here,
it is essential to have better error bounds. In the following sections we
first prove better error bounds. For this, we improve the error bounds given
in Theorem 1 by including a component which takes into account the rate of
decay of the singular values. The bound is then applied to the large and
practically important class of matrices (relating to smooth random fields and
Green’s functions) which have singular values of the form
$\sigma_{k}=O(k^{-s})$. We also provide a new algorithm which has very similar
properties to the maximal $r$-volume algorithms but which is based on the
standard maximal volume approach. We prove that this approach has similar
properties to the algorithm from [7]for symmetric positive definite matrices.
However, we were not able to prove the same bounds for the case of non-
symmetric positive matrices. The proof in the symmetric case relies
substantially on Weyl’s lemma states that the eigenvalues of a principal
submatrix of a symmetric matrix $M$ is bounded by corresponding eigenvalues of
the matrix $M$. An extension of Weyl’s lemma to singular values does not in
general lead to useful bounds of the singular values of submatrices and the
results for the symmetric positive definite case cannot be easily generalised.

Note that an error bound for Schatten-1 norm and symmetric positive symmetric
matrices has been given in [5]. It can be seen that the Schatten-1 norm is
well-defined for matrices with singular values $\sigma_{k}=O(k^{-s})$ where
$s>1$. (Note that it is also defined for other classes of matrices but the
class mentioned is the one of interest here.) In [5], a totally different
approach is used to obtain the error bounds which improve over the standard
bounds of the form $(r+1)\sigma_{r+1}$.

##  2 The Positive Definite Case

In this section we improve the bound provided by Theorem 1 for the case where
the matrix $M$ is symmetric positive definite. Let $M$ be of the form

$M=\begin{bmatrix}A&B\\\ B^{T}&D\end{bmatrix}.$

As $M$ is positive definite, so is $A$. Consequently, the rank of
$A\in\mathbb{R}^{p,p}$ is $r=p$. We assume that (after a suitable symmetric
permutation of rows and columns) $A$ is a principle submatrix of $M$ with
maximal volume. The pseudo-skeleton approximation takes the form

$\widehat{M}=\begin{bmatrix}A\\\
B^{T}\end{bmatrix}A^{-1}\begin{bmatrix}A&B\end{bmatrix}.$

In the following we utilise the harmonic mean of the eigenvalues
$\lambda_{1},\ldots,\lambda_{r+1}$ defined as

$H(\lambda_{1},\ldots,\lambda_{r+1})=\frac{r+1}{\lambda_{1}^{-1}+\cdots+\lambda_{r+1}^{-1}}.$

We then introduce parameters $\zeta_{r}(M)$ for $r=1,\ldots,n$ which
characterise the decay of the singular values of $M$. We define them as

$\zeta_{r}(M):=\frac{H(\lambda_{1},\ldots,\lambda_{r+1})}{\lambda_{r+1}}.$

One can see that $1\leq\zeta_{r}(M)\leq r+1$. Values of $\zeta_{r}(M)$ close
to $r+1$ correspond to fast decay and values close to one to slow decay of the
eigenvalues of $M$.

######  Theorem 3.

Let $M\in\mathbb{R}^{n,n}$ be a symmetric positive definite matrix and let
$\widehat{M}$ be a maximal volume pseudo skeleton approximation of $M$ with
parameters $p=q$. Then $r=\operatorname{rank}(\widehat{M})=p$ and

$\left\|M-\widehat{M}\right\|_{C}\leq\zeta_{r}(M)\,\lambda_{r+1}.$

###### Proof.

Recall that $A$ is positive definite with rank $r=p$.

We first consider the case $n=p+1$ such that

$M=\begin{bmatrix}A&b\\\ b^{T}&d\end{bmatrix}$

for some $b\in\mathbb{R}^{n}$ and $d\in\mathbb{R}_{+}$. Consequently,

$\widehat{M}=\begin{bmatrix}A\\\
b^{T}\end{bmatrix}A^{-1}\begin{bmatrix}A&b\end{bmatrix}$

By direct computation one obtains

$\|M-\widehat{M}\|_{C}=d-b^{T}A^{-1}b.$

Furthermore, Schur’s formula yields

$d-b^{T}A^{-1}b=\frac{\operatorname{det}M}{\operatorname{det}A}.$

As $M$ has full rank $r+1$, it’s inverse exists and has diagonal elements

$M^{-1}_{i,i}=\frac{(\operatorname{adj}M)_{i,i}}{\operatorname{det}M}$

(by Cramer’s rule) where the $i$-th diagonal elements of the adjugate
$\operatorname{adj}M$ are the determinants of the principle $r$ by $r$ sub-
matrices of $M$ obtained by omitting row $i$ and column $i$ from $M$. As $A$
is the principle sub-matrix with maximal determinant one has

$(\operatorname{adj}M)_{i,i}\leq(\operatorname{adj}M)_{r+1,r+1}=\operatorname{det}A$

and consequently

$\operatorname{trace}{(\operatorname{adj}M)}\leq(r+1)\operatorname{det}A.$

As $M^{-1}=(\operatorname{det}M)^{-1}\operatorname{adj}M$ (by Cramer’s rule)
one then gets

$d-b^{T}A^{-1}b=\frac{\operatorname{det}M}{\operatorname{det}A}\leq\frac{r+1}{\operatorname{trace}M^{-1}}$

from which the claimed bound follows as $M$ is invertible.

The general case is then obtained as follows. Let the matrices $B$ and $D$
given by the block partitioning of the matrix $M$:

$M=\begin{bmatrix}A&B\\\ B^{T}&D\end{bmatrix}.$

Then the Chebyshev norm of the error of the rank $r$ pseudo skeleton
approximation can be seen to be the Chebyshev norm of the Schur complement of
$A$. As $M$ is positive definite, so is the Schur complement. Thus the maximal
elements of the Schur complement are positive and diagonal and so

$\lVert
M-\widehat{M}\rVert_{C}=\max_{i=1,\ldots,n-r}(d_{i,i}-b_{i}^{T}A^{-1}b_{i})$

where the $b_{i}$ are the $i$-th columns of $B$.

Now let
$k=\operatorname{argmax}_{i=1,\ldots,n-r}(d_{i,i}-b_{i}^{T}A^{-1}b_{i})$ and

$Y=\begin{bmatrix}A&b_{k}\\\
b_{k}^{T}&d_{k,k}\end{bmatrix}\in\mathbb{R}^{r+1,r+1}$ (2)

As $Y$ is an $r+1$ by $r+1$ principle sub-matrix of $M$, the matrix $Y$ is
positive definite. Furthermore, $A$ is also a maximal volume principal sub-
matrix of $Y$ and hence

$\widehat{Y}=\begin{bmatrix}A\\\
b_{k}^{T}\end{bmatrix}A^{-1}\begin{bmatrix}A&b_{k}\end{bmatrix}$

is a maximal volume pseudo skeleton approximation of $Y$. One then has

$\lVert M-\widehat{M}\rVert_{C}=d_{k,k}-b_{k}^{T}A^{-1}b_{k}=\lVert
Y-\widehat{Y}\rVert_{C}.$ (3)

From the case $n=p+1$ considered above it follows that

$\|Y-\widehat{Y}\|_{C}\leq\frac{r+1}{\lambda_{1}(Y)^{-1}+\cdots+\lambda_{r+1}(Y)^{-1}}.$
(4)

As $Y$ is a principle sub-matrix of $M$ a consequence of the interlacing
theorem for eigenvalues [8] is

$\lambda_{i}(Y)\leq\lambda_{i}(M),\quad i=1,\ldots,r+1$

from which one directly gets

$\|Y-\widehat{Y}\|_{C}\leq\frac{r+1}{\lambda_{1}(M)^{-1}+\cdots+\lambda_{r+1}(M)^{-1}}$

and the claimed bound follows from equation (3). ∎

A direct consequence is that for a large class of matrices one can obtain
errors which up to a constant are of the same size as the errors of the
singular value based approach.

######  Corollary 1.

Let $M\in\mathbb{R}^{n,n}$ be symmetric positive definite and let
$\widehat{M}$ be the maximal volume pseudo-skeleton approximation with rank at
most $r$ and parameters $p=r$ and $q$ as established in Definition (1).
Furthermore, let the eigenvalues $\lambda_{k}$ of $M$ satisfy

$C_{1}\,k^{-s}\leq\lambda_{k}\leq C_{2}\,k^{-s}$

for some positive real numbers $C_{1},C_{2}$ and $s>0$ and $k=1,2,3,\ldots$.
Then

$\left\|\widehat{M}-M\right\|_{C}\leq c\,\lambda_{r+1}$ (5)

with $c=(s+1)C_{2}/C_{1}$.

###### Proof.

From the assumptions on the decay of the eigenvalues one gets

$\displaystyle\zeta_{r}(M)$
$\displaystyle=\frac{H(\lambda_{1},\ldots,\lambda_{r+1})}{\lambda_{r+1}}$
$\displaystyle\leq\frac{C_{2}}{C_{1}}\frac{H(1,2^{-s},\ldots,(r+1)^{-s})}{(r+1)^{-s}}$
$\displaystyle=\frac{C_{2}}{C_{1}}\frac{(r+1)^{s+1}}{(1+2^{s}+\cdots+(r+1)^{s})}$
$\displaystyle\leq\frac{C_{2}}{C_{1}}\frac{(r+1)^{s+1}}{(r+1)^{s+1}/(s+1)}=\frac{C_{2}}{C_{1}}(s+1).$

Here the last inequality is obtained by bounding the sum in the denominator by
an integral. The claimed result follows. ∎

We now propose a rank $r$ approximation which is based on the maximal volume
approximation with rank $r<p$ which is obtained using a truncated singular
value decomposition. Corollary 2 provides the details together with a proof of
an error bound. Note that in the following the parameter $r$ is not the rank
of the maximal volume pseudo skeleton approximation but is chosen
independently satisfying $r<p$ and $\lambda_{r+1}>0$.

######  Corollary 2.

Let $M\in\mathbb{R}^{n,n}$ be a symmetric positive definite matrix and let
$\widehat{M}$ be a maximal volume pseudo skeleton approximation of $M$ with
parameters $p=q$. Furthermore, let
$\widehat{M}_{r}:=\left(\widehat{M}\right)_{r}$ be the approximation based on
the $r$-truncated singular value decomposition of $\widehat{M}$ and $r<p$.
Then

$\lVert\widehat{M}_{r}-M\rVert_{C}\leq\left(\zeta_{p}(M)\frac{\lambda_{p+1}}{\lambda_{r+1}}+1\right)\lambda_{r+1}$

and $\operatorname{rank}(\widehat{M})=r$.

###### Proof.

First, a direct application of Theorem 3 gives

$\lVert\widehat{M}-M\rVert_{C}\leq\zeta_{p}(M)\frac{\lambda_{p+1}}{\lambda_{r+1}}\,\lambda_{r+1}.$

Then, we show

$\lVert\widehat{M}_{r}-\widehat{M}\rVert_{C}\leq\lambda_{r+1}(\widehat{M}_{p})\leq\lambda_{r+1}.$

The first inequality is the standard bound for the singular value based
approximation so that it remains to show that

$\lambda_{r+1}(\widehat{M})\leq\lambda_{r+1}(M).$

As

$M-\widehat{M}=\begin{bmatrix}0&0\\\ 0&D-B^{T}A^{-1}B\end{bmatrix}$

is positive semi-definite as $D-B^{T}A^{-1}B$ is a Schur complement and
$M=\widehat{M}+(M-\widehat{M})$ one obtains
$\lambda_{r+1}(\widehat{M})\leq\lambda_{r+1}(M)$ from Weyl’s inequality. ∎

Using the bound $\zeta_{p}(M)\leq p+1$ one gets

$\lVert\widehat{M}_{r}-M\rVert_{C}\leq\left((p+1)\frac{\lambda_{p+1}}{\lambda_{r+1}}+1\right)\lambda_{r+1}.$

For geometric decay of the eigenvalues, i.e.,

$C_{1}q^{k}\leq\lambda_{k}\leq C_{2}q^{k}$

for some $q\in(0,1)$ and $C_{s}>0$ one gets for a choice of $p=2r$ the bound

$\lVert\widehat{M}_{r}-M\rVert_{C}\leq\left(\frac{C_{2}}{C_{1}}(2r+1)q^{r}+1\right)\lambda_{r+1}.$

It follows that the error bound converges to $\lambda_{r+1}$ for
$r\rightarrow\infty$.

For a slower decay of the eigenvalues of the form

$C_{1}k^{-s}\leq\lambda_{k}\leq C_{2}k^{-s}$

and a choice $p=\alpha(r+1)-1$ for some $\alpha>1$ one obtains from Corollary
2

$\lVert\widehat{M}_{p}-M\rVert_{C}\leq c\lambda_{r+1}$

with

$c=(C_{2}/C_{1})^{2}(s+1)\alpha^{-s}+1.$

It follows that the suggested method has the same error order (in $r$) as the
one based on the truncated singular value decomposition.

The new error bound is substantially better for matrices with eigenvalues
which display moderate decay. In Figure 1 we provide the plots of the bounds
for the case where $\lambda_{k}(M)=k^{-2}$.

$10^{0.0}$$10^{0.5}$$10^{1.0}$$10^{1.5}$$10^{2.0}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$rank
of approximationerror boundTheorem 1Theorem 3Theorem 4 (square non-symmetric)
Figure 1: Comparison of error bounds for the case $\sigma_{k}(M)=k^{-2}$

Furthermore, the error bound is exact for the limiting case of $M=I$ (where
$I$ is the identity matrix). It follows directly from Theorem 3 that any
pseudo-skeleton approximation of the identity is an optimal approximation in
the Chebyshev norm. While this can be also shown directly, it does not,
however, follow from the theorems mentioned in the introduction.

##  3 The General Case

The analysis of the approximation error for non-symmetric matrices
$M\in\mathbb{R}^{m,n}$ is based on the singular values of $M$. Here we assume
that

$M=\begin{bmatrix}A&B\\\ C&D\end{bmatrix}$

where $A\in\mathbb{R}^{p,q}$ is the $p\times q$ submatrix with maximal rank
which has maximal volume. We assume that the parameters established in
Definition 1 satisfy $p\leq q$. As we are mostly interested in error bounds we
can assume that any given matrix has been permuted such that it has this
property. Furthermore, the case $p>q$ is treated by considering the transpose.

A _pseudo-skeleton approximation_ is then given by

$\widehat{M}=\begin{bmatrix}A\\\
C\end{bmatrix}A^{+}\begin{bmatrix}A&B\end{bmatrix}.$

In the following we will use the function $\zeta_{r}$ introduced in the
previous section. In particular, one has

$\zeta_{r}(M^{T}M)=\frac{H(\sigma_{1}^{2},\ldots,\sigma_{r+1}^{2})}{\sigma_{r+1}^{2}}.$

######  Theorem 4.

Let the matrix $\widehat{M}$ with parameters $p\leq q$ be a maximal volume
pseudo-skeleton approximation of a matrix $M\in\mathbb{R}^{m,n}$ with
$\operatorname{rank}(M)\geq p+1$. Then

$\left\|\widehat{M}-M\right\|_{C}\leq\sqrt{\frac{\zeta_{r}(M^{T}M)}{1-r/(q+1)}}\,\sigma_{r+1}(M).$
(6)

The following lemma is essential for the proof of the main theorem of this
section.

######  Lemma 1.

Let $p\leq q$ be two integers and

$W=\begin{bmatrix}A&b\end{bmatrix}P\in\mathbb{R}^{p,q+1}$

where $P$ is a permutation matrix such that
$\operatorname{vol}(A)\geq\operatorname{vol}(W_{i})$ for all submatrices
$W_{i}\in\mathbb{R}^{p,q}$ of $W$ obtained by omitting the $i$-th column. Then

$\operatorname{vol}(W)\leq\frac{1}{\sqrt{1-p/(q+1)}}\operatorname{vol}(A).$

###### Proof.

The Lemma is a direct consequence of the Cauchy-Binet theorem, see Mikhalev
and Oseledets [6, Lemma 4.1]. Specifically, one gets

$\operatorname{det}(WW^{T})=\frac{1}{q+1-p}\sum_{i=1}^{q+1}\operatorname{det}(W_{i}W_{i}^{T})\leq\frac{q+1}{q+1-p}\operatorname{det}(AA^{T})$

and using the definition of the volume one obtains the claimed bound. ∎

We now proceed with the proof of the theorem. First we prove the case $m=p+1$
$n=q+1$ and then we use this result to prove the bound for general $m>p$ and
$n>q$.

###### Proof of Theorem 4.

Consider the case $m=p+1$ and $n=q+1$. In this case it follows that $M$ has
full rank $p+1=r+1$. As in this case

$M=\begin{bmatrix}A&b\\\ c^{T}&d\end{bmatrix}$

for some vectors $b\in\mathbb{R}^{p}$, $c\in\mathbb{R}^{q}$ and a positive
real number $d$, the pseudo skeleton approximation $\widehat{M}$ satisfies

$\widehat{M}=\begin{bmatrix}A&b\\\ c^{T}A^{+}A&c^{T}A^{+}b\end{bmatrix}.$

It follows that the Chebyshev norm of the error is

$\lVert\widehat{M}-M\rVert_{C}=\max\left(\lVert
u\rVert_{C},\,\lvert\gamma\rvert\right).$ (7)

where $u=(I-AA^{+})\,c$ and $\gamma=d-c^{T}A^{+}b$.

From the definition of the adjugate of a matrix, we have

$\operatorname{det}\left(MM^{T}\right)\left(MM^{T}\right)^{-1}=\operatorname{adj}\left(MM^{T}\right)$

and taking the trace of each side, we obtain

$\operatorname{vol}\left(M\right)^{2}\left\|M^{+}\right\|_{F}^{2}=\operatorname{trace}{\left(\operatorname{adj}\left(MM^{T}\right)\right)}.$

It can be seen that the right hand side consists of the sum of the squares of
the volumes of all submatrices of size $p\times(q+1)$ if $M$. As there are
$r+1$ such submatrices, an application of Lemma 1 gives

$\operatorname{trace}{\left(\operatorname{adj}\left(MM^{T}\right)\right)}\leq\frac{(r+1)(q+1)}{q+1-r}\operatorname{vol}{A}^{2}.$

Thus

$\operatorname{vol}\left(M\right)^{2}\left\|M^{+}\right\|_{F}^{2}\leq\frac{(r+1)(q+1)}{q+1-r}\operatorname{vol}{A}^{2}.$
(8)

Then one gets

$\begin{bmatrix}I&0\\\ -c^{T}A^{+}&1\end{bmatrix}M=\begin{bmatrix}A&b\\\
u^{T}&\gamma\end{bmatrix}$

and, as the determinant of the first factor is one

$\operatorname{vol}(M)=\operatorname{vol}\left(\begin{bmatrix}A&b\\\
u^{T}&\gamma\end{bmatrix}\right)$

and hence

$\operatorname{vol}(M)^{2}=\operatorname{det}(MM^{T})=\operatorname{det}\left(\begin{bmatrix}AA^{T}+bb^{T}&\gamma
b\\\ \gamma b^{T}&\lVert u\rVert_{2}^{2}+\gamma^{2}\end{bmatrix}\right).$

Using the Schur complement of the lower right element of the block $2\times 2$
matrix gives

$\displaystyle\operatorname{vol}(M)^{2}$ $\displaystyle=(\lVert
u\rVert_{2}^{2}+\gamma^{2}))\operatorname{det}\left(AA^{T}+\frac{\lVert
u\rVert_{2}^{2}}{\lVert u\rVert_{2}^{2}+\gamma^{2}}bb^{T}\right).$

It follows that

$\operatorname{vol}(M)^{2}\geq(\lVert
u\rVert_{2}^{2}+\gamma^{2})\operatorname{vol}(A)^{2}.$

Combining this inequality with equation 8 gives

$\displaystyle\lVert\widehat{M}-M\rVert_{c}^{2}$ $\displaystyle=\max(\lVert
u\rVert_{C}^{2},|\gamma\rvert^{2})\leq\lVert u\rVert_{2}^{2}+\gamma^{2}$
$\displaystyle\leq\frac{\operatorname{vol}(M)^{2}}{\operatorname{vol}(A)^{2}}\leq\frac{(r+1)(q+1)}{q+1-r}\,\lVert
M^{+}\rVert_{F}^{-2}.$

Introducing $\zeta_{r}$ provides the claimed bound.

We now consider the case of general $n$ and $m$. The error matrix of the
pseudo skeleton approximation is

$\widehat{M}-M=-\begin{bmatrix}0&0\\\ C(I-AA^{+})&D-CA^{+}B\end{bmatrix}.$

Let $r+i$ be the index of the row of the error which contains the element with
largest absolute value. Furthermore, let $j$ be the column index of of the
column of $D-CA^{+}B$ which contains the largest absolute value. The Chebyshev
norm of the error matrix is then

$\lVert\widehat{M}-M\rVert_{C}=\max\left\\{\lVert
c_{i}^{T}(I-AA^{+})\rVert_{C},\,\lvert
d_{i,j}-c_{i}^{T}A^{+}b_{j}\rvert\right\\}$

where $c_{i}^{T}$ and $b_{j}$ are the $i$-th row of $C$ and $j$-th column of
$B$, respectively.

One can see that the right-hand side of the above error formula is just the
Chebyshev norm of the error of the maximal volume rank $r$ pseudo skeleton
approximation of the matrix

$Z:=\begin{bmatrix}A&b_{j}\\\ c_{i}^{T}&d_{i,j}\end{bmatrix},$ (9)

Now we apply the bound obtained for the special case of $m=p+1$ and $n=q+1$ to
get

$\left\|\widehat{M}-M\right\|_{C}\leq\sqrt{\frac{(r+1)(q+1)/(q+1-r)}{\sigma_{1}^{-2}(Z)+\cdots+\sigma_{r+1}^{-2}(Z)}}.$
(10)

By the interlacing theorem for singular values [8] one has

$\sigma_{k}(Z)\leq\sigma_{k}(M),\quad k=1,\ldots,r+1$

as $Z$ is a submatrix of $M$. The claimed bound then follows directly. ∎

A direct consequence is that for a large class of matrices one can obtain
errors which up to a constant are of the same size as the errors of the
singular value based approach.

######  Corollary 3.

Let the matrix $M\in\mathbb{R}^{m,n}$ with $\operatorname{rank}M\geq r+1$ and
let $\widehat{M}$ be the maximal volume pseudo-skeleton approximation with
rank at most $r$ and parameters $p=r$ and $q$ as established in Definition
(1). Furthermore, let $q=\alpha r-1$ for some rational $\alpha>1$ and let the
singular values $\sigma_{k}$ of $M$ satisfy

$\frac{C_{1}}{k^{2s}}\leq\sigma_{k}^{2}\leq\frac{C_{2}}{k^{2s}}$

for some $s>0$ and $k=1,2,3,\ldots$. Then

$\left\|\widehat{M}-M\right\|_{C}^{2}\leq\frac{\alpha}{\alpha-1}\frac{C_{2}}{C_{1}}(2s+1)\,\sigma_{r+1}(M)^{2}.$
(11)

###### Proof.

The error bound of Theorem 4 has the three factors $1/\sqrt{1-r/(q+1)}$,
$\sqrt{\zeta_{r}(M^{T}M)}$ and $\sigma_{r+1}(M)$. The choice of $q$ ensures
that the first factor is

$1/\sqrt{1-r/(q+1)}=1/\sqrt{1-1/\alpha}.$

Taking the square gives the first factor of the bound of the corollary.

Then we have for the squared second factor

$\displaystyle\zeta_{r}(M^{T}M)$
$\displaystyle=\frac{H(\sigma_{1}^{2},\ldots,\sigma_{r+1}^{2})}{\sigma_{r+1}^{2}}$
$\displaystyle\leq\frac{C_{2}}{C_{1}}\frac{H(1,2^{-2s},\ldots,(r+1)^{-2s})}{(r+1)^{-2s}}$
$\displaystyle=\frac{C_{2}}{C_{1}}\frac{(r+1)^{2s+1}}{(1+2^{2s}+\cdots,+(r+1)^{2s})}$
$\displaystyle\leq\frac{C_{2}}{C_{1}}\frac{(r+1)^{2s+1}}{(r+1)^{2s+1}/(2s+1)}=\frac{C_{2}}{C_{1}}(2s+1).$

Here the last inequality is obtained by bounding the sum in the denominator by
an integral. The claimed result follows. ∎

Using the same approach as in as Corollary 2 one gets

$\lVert\widehat{M}_{r}-M\rVert_{C}\leq\left(\sqrt{\zeta_{p}(M^{T}M)}\frac{\sigma_{p+1}}{\sigma_{r+1}}+\frac{\sigma_{r+1}(\widehat{M})}{\sigma_{r+1}}\right)\sigma_{r+1}.$

An application of Weyl’s lemma provides
$\sigma_{r+1}(\widehat{M})\leq\sigma_{r+1}(M)+\lVert\widehat{M}-M\rVert_{2}.$
The problem is that for large matrices the spectral norm can be very large
compared to the Chebyshev norm, see [7] and in particular Theorem 2 in that
paper for more details so that Corollary 2 cannot be easily generalised to the
non-symmetric case short of assuming a condition like
$\sigma_{r+1}(\widehat{M})\leq C\sigma_{r+1}$ for some $C>1$.

##  4 Concluding Remarks

Chebyshev matrix approximation is very useful as it provides error bounds for
the matrix elements. Unlike in the case of $\ell_{2}$ approximation, little is
known about the optimal errors (Chebyshev singular values) and there is no
known exact algorithm. The commonly used error bounds for maximal volume
pseudo skeleton approximations are both tight and practically useful for fast
decaying singular values. However, they are less accurate and not useful in
the case where the singular values decay slowly, e.g. where
$\sigma_{k}=O(k^{-2})$ for small $s$. Continuing on our work in [5] we have
presented new improved error bounds and in particular demonstrated their
improvement for matrices with slowly decaying singular values.

In [4] the authors have presented a new algorithm which combines a pseudo
skeleton approximation with truncated singular value decomposition of this
approximation. As noted previously, they show that this new method provides
approximations which are up to a constant as good as the one based on the
truncated singular value decomposition. The method is based on computing a
pseudo skeleton approximation with maximal $r$-volume. Here we present a
similar approach but use a traditional maximal volume pseudo skeleton
approximation instead. We provide the new improved error bounds for this
method which, at least in the symmetric positive definite case, has similar
properties to those one proposed in˜[4]. We also provide bounds of this method
for the non-positive definite case but they do depend on the singular values
of the pseudo skeleton approximations. Further research may further clarify
this case.

The bounds discussed so far have been all in terms of the singular values
which are the bounds of best approximations using Schatten norms. A next step
would be bounds based on best Chebyshev approximations. A good first
collection of algorithms and results for pseudo-skeleton matrix approximations
has been published in [10] during the revision of this manuscript. An
extension of the research in pseudo-skeleton approximation has considered the
approximation of tensors, see [3].

## References

  * [1] Achiya Dax  “On extremum properties of orthogonal quotients matrices”  In _Linear Algebra and its Applications_ 432.5, 2010, pp. 1234–1257  DOI: 10.1016/j.laa.2009.10.034
  * [2] S. Goreinov and E. Tyrtyshnikov  “The maximal-volume concept in approximation by low-rank matrices”  In _Contemporary Mathematics_ 280 Providence, Rhode Island: American Mathematical Society, 2001, pp. 47–51  DOI: 10.1090/conm/280/4620
  * [3] S.. Goreinov  “On cross approximation of multi-index arrays”  In _Doklady Mathematics_ 77.3, 2008, pp. 404–406  DOI: 10.1134/S106456240803023X
  * [4] S.. Goreinov and E.. Tyrtyshnikov  “Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm”  In _Doklady Mathematics_ 83.3, 2011, pp. 374–375  DOI: 10.1134/S1064562411030355
  * [5] Markus Hegland and Frank Hoog  “Low rank approximation of positive semi-definite symmetric matrices using Gaussian elimination and volume sampling”, 2020  arXiv:2011.14626 [math.NA]
  * [6] A. Mikhalev and I.V. Oseledets  “Rectangular maximum-volume submatrices and their applications”  In _Linear Algebra and its Applications_ 538, 2018, pp. 187–211  DOI: https://doi.org/10.1016/j.laa.2017.10.014
  * [7] A.I. Osinsky and N.L. Zamarashkin  “Pseudo-skeleton approximations with better accuracy estimates”  In _Linear Algebra and its Applications_ 537, 2018, pp. 221–249  DOI: 10.1016/j.laa.2017.09.032
  * [8] João Filipe Queiró  “On the interlacing property for singular values and eigenvalues”  In _Linear Algebra and its Applications_ 97, 1987, pp. 23–28  DOI: https://doi.org/10.1016/0024-3795(87)90136-4
  * [9] O. Roy and M. Vetterli  “The effective rank: A measure of effective dimensionality”  In _2007 15th European Signal Processing Conference_ , 2007, pp. 606–610
  * [10] N.L. Zamarashkin, S.V. Morozov and E.E. Tyrtyshnikov  “On the Best Approximation Algorithm by Low-Rank Matrices in Chebyshev’s Norm”  In _Comput. Math. and Math. Phys._ 62, 2022, pp. 701–718  URL: https://doi.org/10.1134/S0965542522050141