text:
\begin{document}
\title{A Matrix Generalization of \\the Hardy-Littlewood-P\'olya Rearrangement Inequality and Its Applications}
\author{Man-Chung Yue\thanks{Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong. E--mail: {\tt manchung.yue@polyu.edu.hk}}}
\date{\today}
\maketitle

\begin{abstract}
Rearrangement inequalities are important tools in mathematical analysis and have found applications to many different areas.
This paper proves a new matrix rearrangement inequality:
\begin{equation*}
\sum_{i=1}^n f\left(\sigma_i (A)\sigma_{n-i+1} (B)\right) \le \sum_{i=1}^n f\left(\sigma_i (AB)\right) \le \sum_{i=1}^n f\left(\sigma_i (A)\sigma_i (B)\right),
\end{equation*}
for any matrices $A,B\in\mathbb{R}^{n\times n}$ and differentiable function $f$ such that $s\mapsto sf'(s)$ is monotonically increasing.
An important tool in the proof of the above inequality is a first-order perturbation formula for a certain class of matrix functions, which could be of independent interests. Applications of the new matrix rearrangement inequality to the Schatten quasi-norms, the affine-invariant geometry and log-determinant divergences for positive definite matrices are also presented.
\end{abstract}

\bigskip
\keywords{Matrix Rearrangement Inequality, Matrix Perturbation, Schatten Norms, Affine-Invariant Metric, Log-Determinant Divergences}

\section{Introduction}
The well-known Hardy-Littlewood-P\'olya rearrangement inequality \cite{hardy1952inequalities} states that for any vectors $u, v\in \mathbb{R}^n$,
\begin{equation}\label{ineq:HLP}
\sum_{i=1}^n u^\downarrow_i v^\uparrow_i \le \sum_{i=1}^n u_i v_i\le   \sum_{i=1}^n u^\downarrow_i v^\downarrow_i ,
\end{equation}
where $u^\downarrow$ and $v^\downarrow$ ($u^\uparrow$ and $v^\uparrow$) are the vectors with entries of $u$ and $v$ sorted in non-increasing (non-decreasing) order, respectively.
For positive vectors, a generalization of inequality~\eqref{ineq:HLP} is obtained in \cite{london1970rearrangement}, see also \cite[Example 3]{vince1990rearrangement}.
\begin{thm}[London~{\cite[Theorem 2]{london1970rearrangement}}]
\label{thm:London}
Let $u \in \mathbb{R}_{++}^n$,  $v\in \mathbb{R}_+^n$ and  $f : \mathbb{R}_+ \ra \mathbb{R}$ be any convex such that $f(s) \ge f(0)$ for any $s \ge 0$. Then,
\begin{equation*}\label{ineq:London}
\sum_{i = 1}^n f (u_i^\downarrow v_i^\uparrow ) \le \sum_{i = 1}^n f \left(u_i v_i \right) \le \sum_{i = 1}^n f (u_i^\downarrow v_i^\downarrow ).
\end{equation*}
\end{thm}

On the other hand, there are also various generalizations of inequality~\eqref{ineq:HLP} to the matrix case, with the entries of vectors replaced by the eigenvalues $\lambda_i (\cdot)$ or singular values $\sigma_i (\cdot)$ of matrices. One such example is the following result.
\begin{thm}[{Carlen and Lieb~\cite[Theorems 3.1-3.2]{carlen2006some}\footnote{In \cite[Theorems 3.1-3.2]{carlen2006some}, the more general inequalities
\begin{equation*}
\sum_{i = 1}^n \lambda_i^q (A) \lambda_{n - i +1}^{p+q} (B) \le \Tr\big( B^p (B^{\frac{1}{2}} A B^{\frac{1}{2}})^q \big)
\quad
\text{and}
\quad
\Tr\big( B^p (B^{\frac{1}{2}} A B^{\frac{1}{2}})^q \big) \le \sum_{i=1}^n \lambda_i^q (A) \lambda_i^{p+q} (B)
\end{equation*}
for $p \ge 0$ are obtained under the same conditions on $A,B$ and $q$. However, as shown in its proof, the first inequality can be reduced to the case of $p=0$.
}}]
\label{thm:Carlen_Lieb}
Let $A,B\in \mathbb{R}^{n\times n}$ be positive semidefinite matrices and $q \ge 1$. Then, it holds that
\begin{equation*}
\sum_{i = 1}^n \lambda_i^q (A) \lambda_{n - i +1}^q (B) \le \Tr\big( (B^{\frac{1}{2}} A B^{\frac{1}{2}})^q \big) .
\end{equation*}
If $q \ge 1$ is an integer, it also holds that
\begin{equation*}
\Tr\big( (B^{\frac{1}{2}} A B^{\frac{1}{2}})^q \big) \le \sum_{i=1}^n \lambda_i^q (A) \lambda_i^q (B).
\end{equation*}
\end{thm}
The Hardy-Littlewood-P\'olya rearrangement inequality~\eqref{ineq:HLP} and its generalizations, including Theorem~\ref{thm:London} and Theorem~\ref{thm:Carlen_Lieb}, are useful tools in mathematical analysis and have found many applications in both pure and applied mathematics. For example, they have been applied to the study the geometry of Banach spaces~\cite{tomczak1974moduli,carlen2006some}, quantum entanglement~\cite{augusiak2008beyond} and capacity of wireless communication channels~\cite{jorswieck2004performance,dorpinghaus2015log}, to name a few.

The main result Theorem~\ref{thm:matrix_rearrange} of this paper is a new matrix rearrangement inequality, which generalizes both Theorem~\ref{thm:London} (up to smoothness requirement) and Theorem~\ref{thm:Carlen_Lieb}. For the sake of easy discussion and comparisons, here we state a simplified version of Theorem~\ref{thm:matrix_rearrange}.
\begin{thm}
\label{thm:matrix_rearrange_simp}
Let $f: \mathbb{R}_+ \ra \mathbb{R}$ be a continuous function that is differentiable on $\mathbb{R}_{++}$. Suppose that the function $s\mapsto s f'(s)$ is monotonically increasing on $\mathbb{R}_{++}$. Then, for any matrices $A,B\in\mathbb{R}^{n\times n}$, it holds that
\begin{equation*}
\label{ineq:matrix_rearrange}
\sum_{i=1}^n f\left(\sigma_i (A)\sigma_{n-i+1} (B)\right) \le \sum_{i=1}^n f\left(\sigma_i (AB)\right)\le \sum_{i=1}^n f\left(\sigma_i (A)\sigma_i (B)\right).
\end{equation*}
\end{thm}

Theorem~\ref{thm:matrix_rearrange_simp} does not only generalize Theorem~\ref{thm:London} from the vector case to the matrix case but also relaxes the condition on the function $f$ (up to smoothness requirements). Indeed, suppose that the function $f$ in Theorem~\ref{thm:London} is differentiable on $\mathbb{R}_{++}$. Then, we have that for any $s > 0$,
\begin{equation*}
f (s) \ge f(0) \ge f(s) -s f'(s),
\end{equation*}
where the first inequality follows from the assumption of Theorem~\ref{thm:London} and the second inequality from the convexity of $f$. Therefore, $f' (s) \ge 0 $ for any $s > 0$. Hence, for any $s_2 > s_1 > 0$,
\begin{equation}\label{ineq:sf'_monotone}
s_2 f'(s_2) - s_1 f'(s_1) = (s_2 - s_1) f'(s_2) + s_1 (f'(s_2) - f'(s_1)) \ge 0  ,
\end{equation}
where we used the fact that $f'(s_2) \ge f'(s_1)$, due to the convexity of $f$.
This implies that the function $s \mapsto s f' (s)$ is monotonically increasing on $\mathbb{R}_{++}$. Furthermore, as shown in Theorem~\ref{thm:schatten} (see also the remark after the proof of Theorem~\ref{thm:schatten}), Theorem~\ref{thm:matrix_rearrange_simp} is generalization of Theorem~\ref{thm:Carlen_Lieb} as well.

One possibility for proving rearrangement inequalities akin to Theorem~\ref{thm:matrix_rearrange_simp} is by using the majorization theory and Schur-convexity~\cite{marshall2010inequalities}. To put things into perspective, we recall the weak majorization partial order: a vector $u\in\RR^n$ is said to be weakly majorized by another vector $v\in\RR^n$, denoted by $u \prec_w v$, if
\begin{equation*}
\sum_{i=1}^k u_i \le \sum_{i=1}^k v_i \quad\forall k = 1,\dots,n.
\end{equation*}
It is well-known (see, \eg, \cite[Chapter 9, H]{marshall2010inequalities}) that singular values satisfy the weak majorization inequality
\begin{equation*}
\sigma^{\downarrow} (A)\circ \sigma^{\uparrow} (B) \prec_w \sigma (AB) \prec_w \sigma^{\downarrow} (A)\circ \sigma^{\downarrow} (B),
\end{equation*}
where $\circ$ denotes the Hadamard (entry-wise) product.

Therefore, for any function $S:\RR_+^n \ra \RR$ that is order-preserving with respect to the partial order $\prec_w$, we have
\begin{equation*}
 S (\sigma^{\downarrow} (A)\circ \sigma^{\uparrow} (B)) \le S (\sigma (AB)) \le S(\sigma^{\downarrow} (A)\circ \sigma^{\downarrow} (B)) .
\end{equation*}
However, the results \cite[Chapter 3, A.8., C.1.b. and C.1.d.]{marshall2010inequalities} show that the function considered in this paper, \ie,
\begin{equation*}
S(u) = \sum_{i = 1}^n f\left( u_i \right),
\end{equation*}
is order-preserving with respect to $\prec_w$ if and only if $f$ is convex and increasing, which implies the condition on $f$ in Theorem~\ref{thm:matrix_rearrange_simp} by inequality~\eqref{ineq:sf'_monotone}.

By contrast, functions $f$ satisfying the condition in Theorem~\ref{thm:matrix_rearrange_simp} are not necessarily convex nor increasing. This shows that our approach yields more general rearrangement inequalities for singular values than those by using the majorization theory and Schur-convexity.

The rest of the paper is organized as follows. Section~\ref{sec:prelim} prepares some auxiliary results. A key technical result Theorem~\ref{thm:pert} in this section is a first-order perturbation formula for a certain class of matrix functions, which could be of independent interests. The main result Theorem~\ref{thm:matrix_rearrange} and its extension to rectangular matrices will be proved in Section~\ref{sec:main}. In Section~\ref{sec:applications}, we will present several applications of the main result Theorem~\ref{thm:matrix_rearrange}. These applications are related to the Schatten quasi-norm (see Section~\ref{subsec:schatten}), the affine-invariant Riemannian geometry (see Section~\ref{subsec:FR_RG}) and the Alpha-Beta log-determinant divergences (see Section~\ref{subsec:ABLD}) for positive definite matrices.

\subsection{Notations}
The sets of non-negative and positive real numbers are denoted by $\mathbb{R}_+$ and $\mathbb{R}_{++}$, respectively.
Let $u\in \mathbb{R}^n$. The $n\times n$ diagonal matrix with the $i$-th diagonal entry given by $u_i$ is denoted by $\Diag(u)$. Also, the notations $u^\downarrow$ and $u^\uparrow$ denote the vectors with entries of $u$ sorted in non-increasing and non-decreasing orders, respectively.
The sets of $n\times n$ symmetric matrices, positive definite matrices and orthogonal matrices are denoted by $\mathbb{S}_n$, $\mathbb{P}_n$ and $\mathbb{O}_n$, respectively. Occasionally, we also write $A \succ 0$ to denote that $A$ is positive definite.
Throughout the paper, we always assume that $m$ and $n$ are positive integers and $m\le n$. For any matrix $X\in\RR^{m\times n}$, we denote by $\sigma(X) = (\sigma_1 (X), \dots, \sigma_m(X))^\top$ the vector of singular values sorted in non-increasing order.
Also, for any $X\in\mathbb{S}_n$, we denote by $\lambda (X) = (\lambda_1(X),\dots,\lambda_n(X) )^\top$ the vector of eigenvalues sorted in non-increasing order.

\section{Auxiliary Results}
\label{sec:prelim}
In this section, we prepare a few technical tools for the proofs of our main result.
For simplicity, given any real-valued function $f$, we let $S_f:\mathbb{R}^{m\times n} \ra \mathbb{R}$ be the function defined by
\begin{equation*}
S_f (X) = \sum_{i = 1}^m f\left(\sigma_i(X) \right), \quad X\in\mathbb{R}^{m\times n}.
\end{equation*}
The following theorem provides a first-order perturbation formula for $S_f$, which could also be of independent interests. In the sequel, we denote by $\partial S_f$ the limiting subdifferential (or simply called the subdifferential) of $S_f$. For the definition of the limiting subdifferential, see, \eg, \cite[Definition 8.3(b)]{rockafellar2009variational}.
\begin{thm}\label{thm:pert}
Let $f:\mathbb{R}_{++} \ra \RR$ be a differentiable function and $X\in\RR^{m\times n}$ be a full-rank matrix, \ie, $\Rank(X)=m$. Then, for any $\Delta \in \partial S_f(X)$, $Y\in\RR^{m\times n}$ and sufficiently small $\epsilon>0$, we have
\begin{equation*}
S_f(X+\epsilon Y) = S_f(X) + \epsilon\langle \Delta , Y \rangle + o(\epsilon).
\end{equation*}
\end{thm}
\noindent A similar result is obtained in \cite[Theorem 2]{yue2016perturbation}. Unfortunately, the proof of \cite[Theorem 2]{yue2016perturbation} is flawed since the full-rank assumption on $X$ was not imposed, which is necessary as explained after the proof. That said, the proof here is different from that in \cite{yue2016perturbation} and makes explicit connection to the limiting subdifferential $\partial S_f$ of $S_f$, a feature absent from the proof of \cite[Theorem 2]{yue2016perturbation}.

To prove Theorem~\ref{thm:pert}, we recall a few well-known results in matrix theory.
The first one is a characterization of the limiting subdifferential of $S_f$.
\begin{prop}[{Lewis and Sendov~\cite[Theorem 7.1]{lewis2005nonsmooth}}]
\label{prop:subddif_S_f}
Let $f:\mathbb{R}_{++} \ra \RR$ be a differentiable function. For any $X\in\mathbb{R}^{m\times n}$, the limiting subdifferential $\partial S_f(X)$ of $S_f$ at $X$ is given by
\begin{equation*}
\partial S_f(X) = \left\lbrace U \left( \Diag\left(f'\left(\sigma(X)\right)\right)\ \   0 \right) V^\top : (U,V)\in \mathbb{O}^X \right\rbrace,
\end{equation*}
where
\begin{equation*}
\mathbb{O}^X \coloneqq \left\lbrace (U,V)\in \mathbb{O}_m\times \mathbb{O}_n: U \left( \Diag(\sigma(X)) \ \  0 \right) V^\top = X \right\rbrace,
\end{equation*}
and $f'\left(\sigma(X)\right)$ is the vector obtained by applying $f'$ entry-wise to the vector $\sigma(X)$.
\end{prop}
\noindent The original result~\cite[Theorem 7.1]{lewis2005nonsmooth} actually holds for non-smooth functions defined on $\RR_+$. But the version stated in Proposition~\ref{prop:subddif_S_f} suffices for our purpose.

Let $\Xi:\RR^{m\times n} \ra \mathbb{S}_{m+n}$ be the linear map defined by
\begin{equation*}
\Xi(Y) = \begin{pmatrix}
0 & Y \\
Y^\top & 0
\end{pmatrix},\quad Y\in\RR^{m\times n}.
\end{equation*}
The following proposition shows that the singular values and singular vectors of $Y$ are intimately related to the eigenvalues and eigenvectors of $\Xi (Y)$, respectively.
\begin{prop}[{Stewart~\cite[Chapter I, Theorem 4.2]{stewart1990matrix}}]
\label{prop:sym}
Let $X \in \RR^{m\times n}$ be a given matrix with singular value decomposition $X = U \left( \Sigma \ \  0 \right) \left(  V^1 \ \  V^2  \right)^\top$, where $\Sigma = \Diag (\sigma(X))$, $V^1 \in \RR^{n \times m}$ and $V^2 \in \RR^{n \times (n-m)}$. The matrix $\Xi(X)$ admits the eigenvalue decomposition
\begin{equation}\label{eq:1}
\Xi(X) = W
\begin{pmatrix}
\Sigma & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & -\Sigma
\end{pmatrix}
W^\top,
\end{equation}
where
\begin{equation*}
W = \frac{1}{\sqrt{2}}
\begin{pmatrix}
 U & 0 & U \\
 V^1 & \sqrt{2}V^2 & -V^1
\end{pmatrix} \in \mathbb{O}_{m+n}.
\end{equation*}
In particular, $0$ is an eigenvalue of $\Xi(X)$ of multiplicity at least $n-m$, and the remaining $2m$ eigenvalues of $\Xi(X)$ are $\pm \sigma_1(X),\ldots,\pm \sigma_m(X)$.
\end{prop}

Finally, we also need the following perturbation formula for singular values.
\begin{prop}[{Lewis and Sendov~\cite[Section 5.1]{lewis2005nonsmoothII}}]
\label{prop:singval-perturb}
Let $X, Y \in \RR^{m\times n}$. Suppose that $X$ has $\ell +1$ distinct singular values for some $\ell\in\{0,1\ldots,m-1\}$ and that they are arranged as follows:
\begin{equation} \label{eq:singval-not}
\begin{array}{cccccc}
& \sigma_{i_0}(X) &=& \cdots &=& \sigma_{i_1-1}(X) \\
\noalign{\smallskip}
> & \sigma_{i_1}(X) &=& \cdots &=& \sigma_{i_2-1}(X) \\
\noalign{\smallskip}
& & & \vdots & & \\
> & \sigma_{i_j}(X) &=& \cdots &=& \sigma_{i_{j+1}-1}(X) \\
\noalign{\smallskip}
& & & \vdots & & \\
> & \sigma_{i_\ell}(X) &=& \cdots &=& \sigma_{i_{\ell+1}-1}(X),
\end{array}
\end{equation}
where $1 = i_0 < i_1<\cdots<i_\ell <i_{\ell+1}=m+1$.
Then, for any $\epsilon>0$, $j\in\{0,1,\ldots, \ell\}$, and $i \in \{i_j,\ldots,i_{j+1}-1\}$, we have
\begin{equation*} \label{eq:sv-perturb}
\sigma_i(X+ \epsilon Y) = \sigma_i(X) + \epsilon \cdot \lambda_{i-i_j+1}\left( (W^j)^\top \Xi(Y) W^j \right) + O(\epsilon^2),
\end{equation*}
where $W^j$ is an $(m+n) \times m_j$ matrix whose columns are the eigenvectors associated with the eigenvalue $\sigma_{i_j} (X)$ of $\Xi(X)$ (see Proposition~\ref{prop:sym}) and $m_j$ is the multiplicity of the eigenvalue $\sigma_{i_j} (X)$.
\end{prop}

We now have enough tools at our disposal to prove Theorem~\ref{thm:pert}.

\begin{proof}[Proof of Theorem~\ref{thm:pert}]

Recall the notations from Propositions \ref{prop:subddif_S_f}-\ref{prop:singval-perturb}.
Let $\Delta\in\partial S_f(X)$. By Proposition~\ref{prop:subddif_S_f}, there exist a matrix $V^1\in \RR^{n\times m}$ with orthonormal columns and an orthogonal matrix $U\in \mathbb{O}_m$ such that
\begin{equation*}
U\Diag(\sigma(X)){V^1}^\top = X \quad\text{and}\quad \Delta = U\Diag\left(f'(\sigma(X))\right){V^1}^\top.
\end{equation*}
Next, for any $j = 0,\dots,\ell$, let $U^j\in \RR^{m\times (i_{j+1}-i_j)}, V^{1,j}\in \RR^{n\times (i_{j+1}-i_j)}$ be matrices whose columns are the left and right singular vectors of $X$ associated the singular value $\sigma_{i_j}(X)$. By definitions,
\begin{equation*}
U = \left(U^0\ \ U^1 \cdots\ \ U^\ell\right)\quad\text{and}\quad V^1 = \left(V^{1,0}\ \  V^{1,1}\cdots\ \  V^{1,\ell}\right).
\end{equation*}
Then, Proposition~\ref{prop:sym} and the definition of $W^j$ imply that
\begin{equation}\label{eq:2}
W^j = \frac{1}{\sqrt{2}}\begin{pmatrix}
U^j\\
V^{1,j}
\end{pmatrix} .
\end{equation}

Since $f$ is differentiable, it follows from Proposition~\ref{prop:singval-perturb} and the Taylor's Theorem that for sufficiently small $\epsilon>0$, $j\in\{0,1,\ldots,\ell\}$, and $i \in \{i_j,\ldots,i_{j+1}-1\}$, we have
\begin{equation}\label{eq:5}
f(\sigma_i( X+\epsilon Y )) = f(\sigma_i( X )) + \epsilon \cdot f'(\sigma_i(X))\cdot \lambda_{i-i_j+1}\left( (W^j)^\top \Xi(Y) W^j \right) + o(\epsilon).
\end{equation}
Summing \eqref{eq:5} over $j\in\{0,1,\ldots,\ell\}$ and $i \in \{i_j,\ldots,i_{j+1}-1\}$,
\begin{equation}\label{eq:3}
\begin{split}
&\, \sum_{i=1}^m f(\sigma_i(X+\epsilon Y)) \\
=&\, \sum_{j=0}^\ell \sum_{i=i_j}^{i_{j+1}-1} f(\sigma_i(X+\epsilon Y)) \\
= &\, \sum_{j=0}^\ell \sum_{i=i_j}^{i_{j+1}-1} f(\sigma_i(X)) + \epsilon  \sum_{j=0}^\ell \sum_{i=i_j}^{i_{j+1}-1}  f'(\sigma_i(X)) \lambda_{i-i_j+1}\left( (W^j)^\top \Xi(Y) W^j \right) + o(\epsilon)\\
= &\, \sum_{i=1}^m f(\sigma_i(X)) + \epsilon \sum_{j=0}^\ell f'(\sigma_{i_j}(X)) \sum_{i=i_j}^{i_{j+1}-1}  \lambda_{i-i_j+1}\left( (W^j)^\top \Xi(Y) W^j \right) + o(\epsilon) \\
= &\, \sum_{i=1}^m f(\sigma_i(X)) + \epsilon \sum_{j=0}^\ell f'(\sigma_{i_j}(X)) \Tr\left( (W^j)^\top \Xi(Y) W^j \right) + o(\epsilon),
\end{split}
\end{equation}
where the second summation in the last line can be computed using \eqref{eq:2} as
\begin{equation}\label{eq:4}
\begin{split}
&\, \sum_{j=0}^\ell f'(\sigma_{i_j}(X))\cdot \Tr\left( (W^j)^\top \Xi(Y) W^j \right) \\
= &\, \frac{1}{2} \left\langle \Xi(Y) , \sum_{j=0}^\ell f'\left(\sigma_{i_j}(X)\right) \begin{pmatrix}
U^j\\ V^{1,j}
\end{pmatrix}
\begin{pmatrix}
U^j\\ V^{1,j}
\end{pmatrix}^\top \right\rangle \\
= &\, \left\langle Y  , \sum_{j=0}^\ell f'\left( \sigma_{i_j}(X) \right) U^j V^{1,j} \right\rangle \\
= &\, \left\langle Y  , U\Diag\left(f'(\sigma_1(X)),\dots,f'(\sigma_m(X))\right){V^1}^\top \right\rangle \\
= &\, \left\langle Y  , U\Diag\left(f'(\sigma(X))\right){V^1}^\top \right\rangle .
\end{split}
\end{equation}
Substituting \eqref{eq:4} into \eqref{eq:3} yields
\begin{align*}
\sum_{i=1}^m f(\sigma_i(X+\epsilon Y)) =&\, \sum_{i=1}^m f(\sigma_i(X)) + \epsilon \left\langle Y  , U\Diag\left(f'(\sigma(X))\right){V^1}^\top \right\rangle + o(\epsilon) \\
= &\, \sum_{i=1}^m f(\sigma_i(X)) + \epsilon \left\langle Y  , \Delta \right\rangle + o(\epsilon) .
\end{align*}
This completes the proof.
\end{proof}

The non-singularity of $X$ is necessary to Theorem~\ref{thm:pert}, even though Propositions~\ref{prop:subddif_S_f}-\ref{prop:singval-perturb} all do not require this assumption.
Indeed, if the matrix $X$ is of rank $r  < m $, then there will be $m-r$ zero eigenvalues $\sigma_{i_\ell}(X) = \cdots = \sigma_{i_{\ell+1}-1}(X)$ of $\Xi(X)$ contained in $\Sigma$, $m-r$ zero eigenvalues $-\sigma_{i_\ell}(X) = \cdots = -\sigma_{i_{\ell+1}-1}(X)$ of $\Xi(X)$ contained in $-\Sigma$, and $n-m$ zero eigenvalues if $X$ is not a square matrix (see equation~\eqref{eq:1}).
Hence, the multiplicity $m_\ell$ of the zero eigenvalues of $\Xi (X)$ is $n+m-2r$. Instead of equation~\eqref{eq:2}, the matrix $W^\ell$ is given by
\begin{equation*}
W^\ell = \frac{1}{\sqrt{2}}
\begin{pmatrix}
 U^\ell & 0 & U^\ell \\
 V^{1,\ell} & \sqrt{2}V^2 & -V^{1,\ell}
\end{pmatrix} \in \mathbb{R}^{(m+n)\times (n+m-2r)}.
\end{equation*}
This causes the breakdown of equation~\eqref{eq:4}. Therefore, we need the assumption that $X$ is full-rank in Theorem~\ref{thm:pert}.

The following vector rearrangement inequality will also be used in the proof of our main result.

\begin{lem}\label{lem:rearrange}
Let $f:\mathbb{R}_{++}\ra \mathbb{R}$ be a differentiable function. The following hold.
\begin{enumerate}[label = (\roman*)]
\item\label{lem:rearrange_i} If the function
$s\mapsto sf'(s)$ is monotonically increasing on $\RR_{++}$,
then
\begin{equation*}
\sum_{i=1}^n f(u^\uparrow_i v^\downarrow_i) \le \sum_{i=1}^n f(u_iv_i)\le   \sum_{i=1}^n f(u^\downarrow_i v^\downarrow_i)\quad\forall u,v\in\mathbb{R}_{++}^n.
\end{equation*}
\item\label{lem:rearrange_ii} If the function
$s\mapsto sf'(s)$ is monotonically decreasing on $\RR_{++}$,
then
\begin{equation*}
\sum_{i=1}^n f(u^\uparrow_i v^\downarrow_i)\ge \sum_{i=1}^n f(u_iv_i) \ge  \sum_{i=1}^n f(u^\downarrow_i v^\downarrow_i)  \quad\forall u,v\in\mathbb{R}_{++}^n.
\end{equation*}
\end{enumerate}
\end{lem}
\begin{proof}
We only prove \ref{lem:rearrange_i} as \ref{lem:rearrange_ii} can be proved similarly.

It suffices to prove that
\begin{equation*}
f(ac)+f(bd)-f(ad)-f(bc)\geq 0\quad \forall a\geq b> 0,\ c\geq d> 0.
\end{equation*}
Towards that end, we define the function $g(t) = f(tc) - f(td)$ for $t >0$. By the assumptions on $f$,
\begin{equation*}
g'(t) = c f'(tc) - d f'(td) = \frac{1}{t} \left( tc f'(tc) - td f'(td) \right) \ge 0\quad \forall t>0.
\end{equation*}
Therefore, for any $c \ge d > 0$, $g$ is monotonically increasing and hence $g(a) \ge g(b)$, which is equivalent to the inequality $f(ac)+f(bd)-f(ad)-f(bc)\ge 0$. This completes the proof.

\end{proof}
By a similar argument as in the introduction, we see that Lemma~\ref{lem:rearrange} is actually a generalization of of Theorem~\ref{thm:London}, up to smoothness requirement.

\section{Main Result}
\label{sec:main}
We are now ready to prove the main result of this paper.
\begin{thm}
\label{thm:matrix_rearrange}
Let $f:\mathbb{R}_{++}\ra \mathbb{R}$ be a differentiable function. Then, the following hold for any non-singular matrices $A,B\in  \RR^{n\times n}$.
\begin{enumerate}[label = (\roman*)]
\item\label{thm:matrix_rearrange_i} If the function $s\mapsto sf'(s)$ is monotonically increasing on $\RR_{++}$, then
\begin{equation*}
\sum_{i=1}^n f\left(\sigma_i (A)\sigma_{n-i+1} (B)\right) \le S_f(AB)\le \sum_{i=1}^n f\left(\sigma_i (A)\sigma_i (B)\right).
\end{equation*}
\item\label{thm:matrix_rearrange_ii} If the function $s\mapsto sf'(s)$ is monotonically decreasing on $\RR_{++}$, then
\begin{equation*}
\sum_{i=1}^n f\left(\sigma_i (A)\sigma_{n-i+1} (B)\right) \ge S_f(AB)\ge \sum_{i=1}^n f\left(\sigma_i (A)\sigma_i (B)\right).
\end{equation*}
\end{enumerate}
If, in addition to the differentiability on $\mathbb{R}_{++}$, $f$ is also defined and continuous from the right at $0$, then \ref{thm:matrix_rearrange_i} and \ref{thm:matrix_rearrange_ii} hold for any matrices $A,B\in  \RR^{n\times n}$.
\end{thm}

\begin{proof}
For the assertions \ref{thm:matrix_rearrange_i} and \ref{thm:matrix_rearrange_ii}, we only prove \ref{thm:matrix_rearrange_i} as \ref{thm:matrix_rearrange_ii} can be proved by using exactly the same arguments.
To prove \ref{thm:matrix_rearrange_i}, let $A,B\in \mathbb{R}^{n\times n}$ be non-singular matrices.
By using the right and left polar decompositions of $A$ and $B$, respectively, we can assume without loss of generality that $A, B\succ 0$. Since the singular values $\sigma_i(\cdot)$ are continuous on $\mathbb{R}^{n\times n}$ (see, \eg, \cite[Chapter IV, Theorem 4.11]{stewart1990matrix}) and $f$ is continuous on $\mathbb{R}_{++}$, we can also assume without loss of generality that the eigenvalues of $A,B$ are all distinct. Furthermore, suppose that \ref{thm:matrix_rearrange_i} holds for any function $f$ such that $s\mapsto sf'(s)$ is strictly increasing on $\RR_{++}$. Then, for any $\tilde{f}$ such that $s\mapsto s \tilde{f}'(s)$ is only monotonically increasing on $\RR_{++}$, we consider the perturbed function $\tilde{f}_\epsilon (s) \coloneqq \tilde{f}(s) + \epsilon s$. For $\epsilon > 0$,
\begin{equation*}
s_2 \tilde{f}_\epsilon' (s_2) - s_1 \tilde{f}_\epsilon' (s_1) = (s_2 - s_1) \tilde{f}_\epsilon'(s_2) + s_1 (\tilde{f}_\epsilon'(s_2) - \tilde{f}_\epsilon'(s_1)) > 0 \quad \forall s_2 > s_1 > 0.
\end{equation*}
Therefore, $s\mapsto s \tilde{f}_\epsilon'(s)$ is strictly increasing on $\RR_{++}$ By supposition, the inequality in \ref{thm:matrix_rearrange_i} holds for $f = \tilde{f}_\epsilon$. Taking limit $\epsilon \searrow 0$, the rearrangement inequality in \ref{thm:matrix_rearrange_i} then holds for $\tilde{f}$ as well. Hence, it suffices to prove \ref{thm:matrix_rearrange_i} for functions $f$ such that $s\mapsto sf'(s)$ is strictly increasing on $\RR_{++}$.

We start with the lower bound of $S_f (AB)$ in \ref{thm:matrix_rearrange_i}.
Let $U_A\Sigma_AU_A^\top$ and $U_B\Sigma_BU_B^\top$ be the eigenvalue decompositions of $A$ and $B$, respectively. Consider the minimization problem
\begin{equation}\label{opt:S_f}
\inf_{U\in \mathbb{O}_n}  S_f \big(\Sigma_AU\Sigma_BU^\top\big).
\end{equation}
By the continuity of $f$ and the singular values $\sigma_i(\cdot)$, the function $U \mapsto S_f\! \left(\Sigma_AU\Sigma_BU^\top\right)$ is continuous on $\mathbb{O}_n$. Since $\mathbb{O}_n$ is compact, a minimizer $Q\in \mathbb{O}_n$ to problem~\eqref{opt:S_f} exists. Then, we have
\begin{equation*}
S_f ( AB ) \geq \min_{U\in \mathbb{O}_n} S_f \big(\Sigma_AU\Sigma_BU^\top\big) = S_f\big(\Sigma_AQ\Sigma_BQ^\top\big).
\end{equation*}
Let
\begin{equation*}
\hat{B} \coloneqq Q\Sigma_BQ^\top \quad\text{and}\quad C \coloneqq \Sigma_A^{\frac{1}{2}}\hat{B}\Sigma_A^{\frac{1}{2}}.
\end{equation*}
Since $A, B \succ 0$, we have that $C \succ 0$ and hence that $\lambda (C) = \sigma (C)$.
Therefore, by Proposition~\ref{prop:subddif_S_f}, we have
\begin{equation*}
\Delta \coloneqq U_C \Diag\left( f' (\lambda(C)) \right)U_C^\top \in \partial S_f (C),
\end{equation*}
where $U_C \Diag(\lambda(C)) U_C^\top$ is the eigenvalue decomposition of $C$. Let $K$ be the commutator of $\hat{B}$ and $C$, \ie,
\begin{equation*}
K \coloneqq \hat{B}\Sigma_A^{\frac{1}{2}}\Delta \Sigma_A^{\frac{1}{2}}-\Sigma_A^{\frac{1}{2}} \Delta \Sigma_A^{\frac{1}{2}}\hat{B},
\end{equation*}
which is a skew-symmetric matrix.
It holds that $ \text{Exp} (\epsilon K)\in \mathbb{O}_n$ for any $\epsilon\in\mathbb{R}$, where $ \text{Exp} (\cdot)$ denotes the matrix exponential. By the continuity of $f$ and the singular values $\sigma_i(\cdot)$ and Theorem~\ref{thm:pert}, we have
\begin{equation*}
\begin{split}
& S_f \big(\Sigma_A \text{Exp} (\epsilon K)\hat{B} \text{Exp} (\epsilon K)^\top\big) \\
= & S_f \big(\Sigma_A(I+\epsilon K)\hat{B}(I-\epsilon K)\big) + o(\epsilon) \\
= & S_f \big(\Sigma_A\hat{B}+\epsilon \Sigma_A(K\hat{B}-\hat{B} K )\big) + o(\epsilon) \\
= & S_f \Big( \Sigma_A^{\frac{1}{2}}\hat{B}\Sigma_A^{\frac{1}{2}}+\epsilon\Sigma_A^{\frac{1}{2}}( K \hat{B}-\hat{B} K )\Sigma_A^{\frac{1}{2}}\Big) + o(\epsilon) \\
= & S_f \Big( \Sigma_A^{\frac{1}{2}}\hat{B}\Sigma_A^{\frac{1}{2}} \Big) + \epsilon\left\langle \Sigma_A^{\frac{1}{2}} K \hat{B}\Sigma_A^{\frac{1}{2}}-\Sigma_A^{\frac{1}{2}}\hat{B} K \Sigma_A^{\frac{1}{2}}, \Delta  \right\rangle + o(\epsilon) \\
= & S_f \Big( \Sigma_A^{\frac{1}{2}}\hat{B}\Sigma_A^{\frac{1}{2}}\Big) + \epsilon\left\langle  K ,\Sigma_A^{\frac{1}{2}} \Delta \Sigma_A^{\frac{1}{2}}\hat{B}-\hat{B}\Sigma_A^{\frac{1}{2}} \Delta \Sigma_A^{\frac{1}{2}}\right\rangle + o(\epsilon) \\
= & S_f \Big( \Sigma_A^{\frac{1}{2}}\hat{B}\Sigma_A^{\frac{1}{2}} \Big)-\epsilon\norm{ K }^2_F + o(\epsilon),
\end{split}
\end{equation*}
where $\norm{\,\cdot\,}_F$ denotes the Frobenius norm.
Therefore, $ K = 0$ because otherwise it would violate the minimality of $Q$ by taking a sufficiently small $\epsilon>0$. Hence, we have that
\begin{equation*}
\hat{B}\Sigma_A^{\frac{1}{2}} \Delta  \Sigma_A^{\frac{1}{2}} =\Sigma_A^{\frac{1}{2}} \Delta  \Sigma_A^{\frac{1}{2}}\hat{B},
\end{equation*}
which is equivalent to
\begin{equation}\label{eq:pf_1}
C \Delta  \Sigma_A = \Sigma_A \Delta C.
\end{equation}
Letting
\begin{equation}\label{def:C_hat}
\hat{C} \coloneqq U_C \Diag\left(\lambda(C) \circ f'(\lambda(C)) \right)U_C^\top ,
\end{equation}
it then follows from the definition of $\Delta$ that
\begin{equation*}
C \Delta
=  U_C \Diag\left(\lambda(C) \circ f'(\lambda(C)) \right)U_C^\top = \hat{C} = U_C \Diag\left(f'(\lambda(C) \circ \lambda(C)) \right)U_C^\top = \Delta C.
\end{equation*}
Thus, equality~\eqref{eq:pf_1} becomes
\begin{equation}\label{eq:7}
\hat{C} \Sigma_A = \Sigma_A \hat{C}.
\end{equation}
In other words, $\hat{C}$ commutes with $\Sigma_A$.
We claim that $C$ also commutes with $\Sigma_A$. To prove the claim, we write the diagonal matrix $\Diag(\lambda (C))$ into the following block-diagonal form:
\begin{equation}\label{eq:diag_form}
\Diag(\lambda(C)) =
\begin{pmatrix}
c_1 I_{n_1} & & \\
 & \ddots & \\
 & & c_\ell I_{n_\ell}
\end{pmatrix},
\end{equation}
where $\ell, n_1,\dots,n_\ell$ are positive integers such that $n_1 +\cdots + n_\ell = n$, and $c_1,\dots, c_\ell $ are distinct real numbers.

Since the function $s\mapsto s f'(s)$ is strictly increasing on $\RR_{++}$,
the diagonal matrix $ \Diag\left(\lambda(C) \circ f'(\lambda(C)) \right)$ takes the same form as \eqref{eq:diag_form}, \ie, there exist distinct numbers $t_1,\dots,t_\ell \in\mathbb{R}$ such that
\begin{equation}\label{eq:diag_form_1}
\Diag\left(\lambda(C) \circ f'(\lambda(C)) \right) =
\begin{pmatrix}
t_1 I_{n_1} & & \\
 & \ddots & \\
 & & t_\ell I_{n_\ell}
\end{pmatrix}.
\end{equation}
From~\eqref{def:C_hat}, \eqref{eq:7} and \eqref{eq:diag_form_1}, we have that
\begin{equation*}
U_C^\top\Sigma_A U_C\begin{pmatrix}
t_1I_{n_1}&&\\
&\ddots&\\
&&t_\ell I_{n_\ell}\\
\end{pmatrix}=\begin{pmatrix}
t_1I_{n_1}&&\\
&\ddots&\\
&&t_\ell I_{n_\ell}\\
\end{pmatrix}U_C^\top\Sigma_A U_C,
\end{equation*}
which implies that the matrix $U_C^\top \Sigma_A U_C$ takes the same block-diagonal form as \eqref{eq:diag_form}, \ie, there exist symmetric matrices $\tilde{A}_1\in\mathbb{R}^{n_1\times n_1},\dots, \tilde{A}_\ell \in \mathbb{R}^{n_\ell \times n_\ell}$ such that
\begin{equation*}
U_C^\top\Sigma_A U_C=\begin{pmatrix}
\tilde{A}_1&&\\
&\ddots&\\
&&\tilde{A}_\ell
\end{pmatrix}.
\end{equation*}
Using the equality
\begin{equation*}
\begin{pmatrix}
\tilde{A}_1&&\\
&\ddots&\\
&&\tilde{A}_\ell
\end{pmatrix}\begin{pmatrix}
c_1I_{n_1}&&\\
&\ddots&\\
&&c_\ell I_{n_\ell }
\end{pmatrix} = \begin{pmatrix}
c_1I_{n_1}&&\\
&\ddots&\\
&&c_\ell I_{n_\ell }
\end{pmatrix}\begin{pmatrix}
\tilde{A}_1&&\\
&\ddots&\\
&&\tilde{A}_\ell
\end{pmatrix},
\end{equation*}
we arrive at
\begin{equation*}
U_C^\top \Sigma_A U_C \Diag(\lambda(C)) = \Diag(\lambda(C)) U_C^\top \Sigma_A U_C .
\end{equation*}
Multiplying the above equality by $U_C$ from the left and $U_C^\top$ from the right, we get
\begin{equation}\label{eq:commute}
\Sigma_A C = C \Sigma_A,
\end{equation}
which proves the claim. Then, it follows from equality~\eqref{eq:commute} and the definition of $C$ that $\Sigma_A \hat{B} = \hat{B} \Sigma_A$. Since $\Sigma_A$ is a diagonal matrix with distinct diagonal entries, the matrix $\hat{B} = Q \Sigma_B Q^\top$ is also diagonal. Hence, the minimizer $Q$ is a permutation matrix. So, there exists a permutation $\pi$ on $\{1,\dots,n\}$ such that
\begin{equation}\label{eq:6}
S_f \big(\Sigma_AQ\Sigma_BQ^\top \big) = \sum_{i = 1}^n f \left( \lambda_i (A) \lambda_{\pi_i}(B) \right).
\end{equation}
Using \eqref{eq:6}, Lemma~\ref{lem:rearrange} and the fact that $A,B\succ 0$, we get
\begin{equation*}
S_f ( A B ) \ge S_f \big(\Sigma_AQ\Sigma_BQ^\top\big) \ge \sum_{i = 1}^n f(\lambda_i(A) \lambda_{n-i+1}(B)) = \sum_{i = 1}^n f(\sigma_i(A) \sigma_{n-i+1}(B))
\end{equation*}
which yields the desired lower bound. The upper bound of $S_f(AB)$ in \ref{thm:matrix_rearrange_i} can be proved similarly by considering the maximization problem
\begin{equation*}
\sup_{U\in \mathbb{O}_n} S_f  \big(\Sigma_AU\Sigma_BU^\top\big),
\end{equation*}
instead of the minimization problem~\eqref{opt:S_f}. Finally, the last statement follows from the right continuity of $f$ at $0$, the continuity of singular values $\sigma_i(\cdot)$, limiting arguments and the statements \ref{thm:matrix_rearrange_i} and \ref{thm:matrix_rearrange_ii}. This completes the proof.

\end{proof}

For statement~\ref{thm:matrix_rearrange_i} (statement~\ref{thm:matrix_rearrange_ii}) in Theorem~\ref{thm:matrix_rearrange}, the upper (lower) bound actually holds even for rectangular matrices.

\begin{coro}\label{coro:rectangular_AB}
Let $f:\mathbb{R}_+ \ra \mathbb{R}$ be a function that is continuous from the right at $0$ and differentiable on $\RR_{++}$. Then, the following hold for any matrices $A,B\in  \RR^{m\times n}$.
\begin{enumerate}[label = (\roman*)]
\item\label{coro:rectangular_AB_i} If the function $s\mapsto sf'(s)$ is monotonically increasing on $\RR_{++}$, then
\begin{equation*}
S_f  \big(A B^\top\big)\le \sum_{i=1}^m f\left(\sigma_i (A)\sigma_i (B)\right).
\end{equation*}
\item\label{coro:rectangular_AB_ii} If the function $s\mapsto sf'(s)$ is monotonically decreasing on $\RR_{++}$, then
\begin{equation*}
S_f  \big(AB^\top\big) \ge \sum_{i=1}^m f\left(\sigma_i (A)\sigma_i (B)\right) .
\end{equation*}
\end{enumerate}
\end{coro}

\begin{proof}
We only prove \ref{coro:rectangular_AB_i} as \ref{coro:rectangular_AB_ii} can be proved by using exactly the same arguments.
Let $A, B\in \mathbb{R}^{m\times n}$. Consider the $(m+n)\times (m+n)$ symmetric matrices
\begin{equation*}
\Xi (A) =
\begin{pmatrix}
0 & A \\
A^\top & 0
\end{pmatrix}
\quad\text{and}\quad
\Xi (B) =
\begin{pmatrix}
0 & B \\
B^\top & 0
\end{pmatrix}.
\end{equation*}
By Proposition~\ref{prop:sym}, we have that for $i = 1, \dots, m$,
\begin{equation*}
\sigma_{2i - 1} ( \Xi(A)) =  \sigma_{2i } (\Xi(A)) =  \sigma_i (A) \quad\text{and}\quad \sigma_{2i - 1} ( \Xi(B)) =  \sigma_{2i } (\Xi(B)) =  \sigma_i (B),
\end{equation*}
and that for $i = 2m+1, \dots, m+n$,
\begin{equation*}
\sigma_i (\Xi(A)) = \sigma_i (\Xi (B)) = 0.
\end{equation*}
Therefore,
\begin{equation}\label{ineq:coro_pf_1}
\sum_{i = 1}^{m+n} f (\sigma_i (\Xi(A)) \sigma_i ( \Xi(B)) )  = 2 \sum_{i = 1}^m f \left( \sigma_i (A) \sigma_i (B) \right) + (n-m) f(0).
\end{equation}
On the other hand, we have
\begin{equation*}
\Xi (A) \Xi (B) =
\begin{pmatrix}
A B^\top & 0 \\
0 & A^\top B
\end{pmatrix},
\end{equation*}
which implies that for $i = 1,\dots, m$,
\begin{equation*}
\sigma_{2i-1} ( \Xi (A) \Xi (B) ) = \sigma_{2i} ( \Xi (A) \Xi (B) ) = \sigma_i \left(A B^\top\right),
\end{equation*}
and that for $i = 2m+1,\dots, m+n$,
\begin{equation*}
\sigma_i ( \Xi (A) \Xi (B) ) = 0.
\end{equation*}
Therefore,
\begin{equation}\label{ineq:coro_pf_2}
\sum_{i=1}^{m+n} f\left( \sigma_i ( \Xi (A) \Xi (B) ) \right)  = 2\sum_{i = 1}^m f\big(\sigma_i\big(A B^\top\big) \big) + (n-m) f(0) .
\end{equation}
Since the function $s\mapsto sf'(s)$ is monotonically increasing on $\RR_{++}$, by the last statement of Theorem~\ref{thm:matrix_rearrange}, we have that
\begin{equation}\label{ineq:coro_pf_3}
\sum_{i=1}^{m+n} f\left( \sigma_i ( \Xi (A) \Xi (B) ) \right) \le \sum_{i = 1}^{m+n} f (\sigma_i (\Xi(A)) \sigma_i ( \Xi(B)) ).
\end{equation}
Substituting equalities~\eqref{ineq:coro_pf_1} and \eqref{ineq:coro_pf_2} into inequality~\eqref{ineq:coro_pf_3}, we obtain
\begin{equation*}
\sum_{i = 1}^m f\big(\sigma_i\big(A B^\top\big) \big) \le \sum_{i = 1}^m f \left( \sigma_i (A) \sigma_i (B) \right).
\end{equation*}
The completes the proof.
\end{proof}

\section{Applications}
\label{sec:applications}

\subsection{Application to the Schatten-$q$ Quasi-Norm}
\label{subsec:schatten}
For $q\ge 1$, the Schatten-$q$ norm is defined as
\begin{equation*}
\norm{X}_q = \sum_{i = 1}^m \sigma_i^q (X), \quad X\in\mathbb{R}^{m\times n}.
\end{equation*}
Here we recall that we assume $m \le n$.
The Banach space associated with the Schatten-$q$ norm for $q \ge 1$ is a classical subject in operator theory and has attracted much research since the forties, see~\cite{schatten1960norm, gohberg1969introduction,tomczak1974moduli}. On the other hand, if $q \in (0,1)$, $\norm{X}_q$ is not longer a norm but only a quasi-norm since it violates the triangle inequality.
Motivated by its proximity to the rank function, the Schatten-$q$ quasi-norm with $q\in (0,1]$ has been extensively used in the studies of low-rank matrix recovery~\cite{rohde2011estimation, yue2016perturbation} over the past decade over so.

As an application of our main result Theorem~\ref{thm:matrix_rearrange}, we obtain the following inequality on the Schatten-$q$ quasi-norm, which could potentially find applications in the analysis of the statistical properties and numerical algorithms of low-rank matrix recovery optimization models based on the Schatten-$q$ quasi-norm.
\begin{thm}
\label{thm:schatten}
Let $A,B\in \mathbb{R}^{m\times n}$ and $q \in \mathbb{R}$. Then, it holds that
\begin{equation*}
 \norm{AB}_q^q \le \sum_{i = 1}^m \sigma_i^q (A) \sigma_{i}^q (B).
\end{equation*}
Furthermore, if $m = n$, \ie, $A$ and $B$ are square matrices, it also holds that
\begin{equation*}
\sum_{i = 1}^n \sigma_i^q (A) \sigma_{n-i+1}^q (B) \le  \norm{AB}_q^q .
\end{equation*}
\end{thm}

\begin{proof}
We first prove the upper bound on $\norm{AB}_q^q$. The case of $q = 0$ is trivial. So, we assume that $q
\neq  0$.
Consider the function $f: \mathbb{R}_+ \ra \mathbb{R} $ defined by $f(s) = s^q$ for $s\in \mathbb{R}_+$. Then, the function $s\mapsto s f'(s) = q s^q$ is obviously increasing on $\mathbb{R}_{++}$. The desired inequality then follows from Corollary~\ref{coro:rectangular_AB}\ref{coro:rectangular_AB_i}.

The lower bound on $\norm{AB}_q^q$ can be proved similarly with using Theorem~\ref{thm:matrix_rearrange}\ref{thm:matrix_rearrange_i} instead of Corollary~\ref{coro:rectangular_AB}\ref{coro:rectangular_AB_i}.
This completes the proof.
\end{proof}

\noindent Note that Theorem~\ref{thm:schatten} holds for arbitrary $q\in \mathbb{R}$, including the $q < 0$. Furthermore, Theorem~\ref{thm:schatten} generalizes Theorem~\ref{thm:Carlen_Lieb} in two senses: from $q \ge 1$ to arbitrary $q\in\mathbb{R}$ and from positive semidefinite matrices to arbitrary square or rectangular matrices.

\subsection{Application to the Affine-Invariant Geometry on $\mathbb{P}_n$}
\label{subsec:FR_RG}

It is well-known that the cone of $n\times n$ positive definite matrices, denoted by $\mathbb{P}_n$, is a differentiable manifold of dimension $n(n+1)/2$, see, \eg, \cite[Chapter 6]{bhatia2009positive}. For any point $A \in \mathbb{P}_n$, the tangent space $T_A \mathbb{P}_n$ at $A$ can be identified with the set of $n\times n$ symmetric matrices $\mathbb{S}_n$. We can equip the cone $\mathbb{P}_n$ with a Riemannian metric called the affine-invariant metric or the Fisher-Rao metric:
\begin{equation*}
\langle X , Y\rangle_A \coloneqq \Tr\left( X A^{-1} Y A^{-1} \right),\quad  X, Y \in T_A \mathbb{P}_n \cong \mathbb{S}_n.
\end{equation*}
Indeed, one can easily check that, given any $A\succ 0$, the map $\langle \cdot , \cdot \rangle_A$ defines a symmetric positive definite bilinear form on $\mathbb{S}_n$. The corresponding Riemannian (geodesic) distance $d_{\mathbb{P}_n}(\cdot, \cdot) $ is given by
\begin{equation*}
d_{\mathbb{P}_n}  (A, B) = \norm{\text{Log} \big(B^{-\frac{1}{2}} A B^{-\frac{1}{2}}\big) }_F, \quad A,B\in \mathbb{P}_n,
\end{equation*}
where $\text{Log}(\,\cdot\, )$ denotes the matrix logarithm. This distance enjoys many interesting properties~\cite[Chapter 6]{bhatia2009positive} and finds applications in diverse areas such as machine learning~\cite{nguyen2019calculating,sra2016geometric}, image and video processing~\cite{dryden2009non,tuzel2008pedestrian} and elasticity theory~\cite{moakher2006closest,neff2014logarithmic}.

We obtain the following lower and upper bounds on $d_{\mathbb{P}_n} (\cdot, \cdot) $.
\begin{coro}\label{coro:R_dist}
For any $A,B\in \mathbb{P}_n$, it holds that
\begin{equation*}
\sum_{i = 1}^n \left( \log  \lambda_i (A) -\log \lambda_i (B)  \right)^2 \le d^2_{\mathbb{P}_n} (A, B) \le  \sum_{i = 1}^n \left( \log  \lambda_i (A) -\log \lambda_{n-i+1} (B)  \right)^2 .
\end{equation*}
\end{coro}
\noindent Corollary~\ref{coro:R_dist} follows immediately by taking $q = 2$ in Theorem~\ref{thm:d_q} below.
To state Theorem~\ref{thm:d_q}, for any $q\ge 1$, we define
\begin{equation*}
d_q (A, B) = \norm{ \text{Log} \big( B^{-\frac{1}{2}} A B^{-\frac{1}{2}} \big) }_q, \quad A,B\in\mathbb{P}_n.
\end{equation*}
It has been proved in \cite[Section 6]{bhatia2009positive} that the function $d_q $ is a distance on $\mathbb{P}_n$ for general $q \ge 1$.

\begin{thm}\label{thm:d_q}
Let $A,B\in \mathbb{P}_n$ and $q \ge 1$. Then, it holds that
\begin{equation*}
\sum_{i = 1}^n \left| \log  \lambda_i (A) -\log \lambda_i (B)  \right|^q \le d^q_q (A, B) \le  \sum_{i = 1}^n \left| \log  \lambda_i (A) -\log \lambda_{n-i+1} (B)  \right|^q .
\end{equation*}
\end{thm}

\begin{proof}
We first assume that $q> 1$. Next, we note that
\begin{equation*}
 d_q^q (A,B)  = \norm{\text{Log}\big( B^{-\frac{1}{2}} A B^{-\frac{1}{2}} \big)}_q^q = \sum_{ i = 1}^n f\big( \sigma_i \big( A B^{-1} \big) \big),
\end{equation*}
where $f:\mathbb{R}_{++} \ra \mathbb{R}$ is the function defined by $f (s) = |\log s|^q$ for $s \in \mathbb{R}_{++}$. It can be easily seen that $f$ is differentiable on $\mathbb{R}_{++}$ and
\begin{equation*}
f' (s) = \begin{cases}
\frac{q}{s} (\log s)^{q-1}, & \text{if } s\ge 1,\\
-\frac{q}{s} (\log \frac{1}{s})^{q-1}, & \text{if } s< 1.
\end{cases}
\end{equation*}
Hence,
\begin{equation}\label{eq:sf'}
s f'(s) = \sgn(\log s)\cdot q |\log s|^{q-1}.
\end{equation}
To show that $s\mapsto s f' (s)$ is monotonically increasing, we let $ s_2 > s_1 > 0$ and consider four different cases: $s_2 \ge 1> s_1 > 0 $, $s_2 > 1\ge s_1 > 0 $, $s_2 > s_1 \ge 1$ and $s_1 < s_2 \le 1$. For the first two cases, by \eqref{eq:sf'}, we have that $s_2 f' (s_2) \ge 0 \ge s_1 f' (s_1)$. For the third case of $s_2 > s_1 \ge 1$, since $f$ is twice differentiable on $(1,\infty)$ and
\begin{equation*}
(sf'(s))' = \left( q (\log s)^{q-1} \right)' = \frac{q(q-1) (\log s)^{q-2}}{s} \ge 0 \quad\forall s> 1,
\end{equation*}
we have $s_2 f' (s_2) \ge s_1 f' (s_1)$. Similarly, for the fourth case of $s_1 < s_2 \le 1$, since $f$ is also twice differentiable on $(0,1)$ and
\begin{equation*}
(sf'(s))' = \left(- q \left(\log \tfrac{1}{s} \right)^{q-1} \right)' = \frac{q(q-1) \left(\log\tfrac{1}{s} \right)^{q-2}}{s} \ge 0\quad\forall s\in (0,1),
\end{equation*}
we have $s_2 f' (s_2) \ge s_1 f' (s_1)$.
Therefore, by Theorem~\ref{thm:matrix_rearrange}\ref{thm:matrix_rearrange_i}, we obtain
\begin{equation*}
\sum_{i=1}^n f\big(\sigma_i (A)\sigma_i (B^{-1})\big) \ge \sum_{ i = 1}^n f\big( \sigma_i \big(A B^{-1} \big) \big) \ge \sum_{i=1}^n f\big(\sigma_i (A)\sigma_{n-i+1} (B^{-1})\big),
\end{equation*}
which is equivalent to
\begin{equation*}
\sum_{i = 1}^n \left| \log  \lambda_i (A) -\log \lambda_i (B)  \right|^q \le d^q_q (A, B) \le  \sum_{i = 1}^n \left| \log  \lambda_i (A) -\log \lambda_{n-i+1} (B)  \right|^q .
\end{equation*}
The case of $q = 1$ follows from limiting arguments. This completes the proof.
\end{proof}

\subsection{Application to the Alpha-Beta Log-Determinant Divergences}
\label{subsec:ABLD}

Divergences, which are measures of dissimilarity of positive definite matrices, play an important role in information geometry and find applications across many areas, see \cite{nielsen2013matrix, cichocki2015log, amari2016information} and the references therein.  As a unification and generalization of many existing divergences in the literature, the family of Alpha-Beta log-determinant divergences (or AB log-det divergences for short) is introduced and studied in \cite{cichocki2015log}. Given any $\alpha, \beta\in \mathbb{R}$ such that $\alpha \beta \neq 0$ and $\alpha + \beta \neq 0$, the AB log-det divergence $D_{\alpha, \beta}(\cdot \| \cdot)$ with parameter $\alpha$ and $\beta$ is defined by
\begin{equation*}
D_{\alpha, \beta}(A \| B) = \frac{1}{\alpha \beta} \log \det\left( \frac{\alpha (B A^{-1})^\beta + \beta (A B^{-1})^{-\alpha}  }{\alpha + \beta} \right), \quad
  A, B \in \mathbb{P}_n.
\end{equation*}
The definition of AB log-det divergences can be extended to the cases of $\alpha \beta= 0$ and/or $\alpha + \beta = 0$ by taking limits and using the L\textsc{\char13}H\^opital's rule. In particular, we have
\begin{equation*}
D_{\alpha, \beta}(A \| B) =
\begin{cases}
\medskip
\displaystyle\frac{1}{\alpha^2} \left( \Tr \big(\big(BA^{-1}\big)^\alpha - I\big) - \alpha \log\det\big(BA^{-1}\big)\right), & \text{if } \alpha\neq 0, \beta = 0, \\

\medskip
\displaystyle\frac{1}{\beta^2} \left( \Tr \big( \big(BA^{-1}\big)^\alpha - I\big) - \beta \log\det\big(BA^{-1}\big)\right), & \text{if } \beta\neq 0, \alpha = 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \log\left( \frac{ \det \big(BA^{-1}\big)^{\alpha} }{ \det \left( I + \log\big(BA^{-1}\big)^\alpha  \right) } \right), & \text{if } \alpha = -\beta \neq 0, \\

\medskip
\displaystyle\frac{1}{2}\norm{\text{Log} \big(BA^{-1}\big) }_F^2, &\text{if } \alpha = \beta = 0.
\end{cases}
\end{equation*}

Many well-known divergences are special cases of the AB log-det divergences, including the squared affine-invariant Riemannian metric (up to re-scaling, see Section~\ref{subsec:FR_RG}) where $\alpha = \beta = 0$, the S-divergence~\cite{sra2016positive} where $\alpha = \beta = \tfrac{1}{2}$ and the Stein's loss~\cite{james1992estimation} (also called the Burg divergence) where $\alpha = 0$ and $\beta = 1$. For more examples of AB log-det divergences, we refer the readers to \cite[Section 3]{cichocki2015log}.

As pointed out in \cite{cichocki2015log}, for any $A,B\in\mathbb{P}_n$, the AB log-det divergence $D_{\alpha, \beta}(A \| B)$ can be expressed via the eigenvalues of the matrix $AB^{-1}$, which coincide with those of the matrix $B^{-\frac{1}{2}} A B^{-\frac{1}{2}}$ and hence are positive. More precisely, it holds that
\begin{equation*}
D_{\alpha, \beta}(A \| B) =
\begin{cases}
\medskip
\displaystyle\frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (AB^{-1}) + \beta \lambda_i^{-\alpha} (AB^{-1}) }{\alpha + \beta} \right), &\text{if } \alpha \beta, \alpha + \beta\neq 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \left( \lambda_i^{-\alpha} (AB^{-1}) - \log\lambda_i^{-\alpha} (AB^{-1}) -1 \right) , & \text{if } \alpha\neq 0, \beta = 0, \\

\medskip
\displaystyle\frac{1}{\beta^2} \sum_{i=1}^n \left( \lambda_i^{\beta} (AB^{-1}) - \log\lambda_i^{\beta} (AB^{-1}) -1 \right), & \text{if } \beta\neq 0, \alpha = 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \log \left( \frac{\lambda_i^\alpha \left( AB^{-1} \right) }{1 + \log \lambda_i^\alpha \left( AB^{-1}  \right)} \right), & \text{if } \alpha = -\beta \neq 0, \\

\medskip
\displaystyle\frac{1}{2}\sum_{i=1}^n \left(\log \lambda_i \big(BA^{-1}\big)\right)^2, &\text{if } \alpha = \beta = 0.
\end{cases}
\end{equation*}

The following upper and lower bounds for the AB log-det divergences are generalizations of the \cite[Corollary 3.8]{sra2016positive}.

\begin{thm}
Let $A,B\in \mathbb{P}_n$ and $\alpha, \beta \in \mathbb{R}$. If $\alpha \beta \ge 0$,
then
\begin{equation*}
D_{\alpha, \beta}(A \| B) \le
\begin{cases}
\medskip
\displaystyle\frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{n-i+1}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{n-i+1}^{\alpha} (B) }{\alpha + \beta} \right), &\text{if } \alpha \beta, \alpha + \beta\neq 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \left( \frac{\lambda_{n-i+1}^{\alpha} (B)}{\lambda_i^{\alpha} (A)}  - \log\left( \frac{\lambda_{n-i+1}^{\alpha} (B)}{\lambda_i^{\alpha} (A)} \right) -1 \right) , & \text{if } \alpha\neq 0, \beta = 0, \\

\medskip
\displaystyle\frac{1}{\beta^2} \sum_{i=1}^n \left( \frac{\lambda_i^{\beta} (A)}{\lambda_{n-i+1}^{\beta} (B)}  - \log\left( \frac{\lambda_i^{\beta} (A)}{\lambda_{n-i+1}^{\beta} (B)} \right) -1 \right), & \text{if } \beta\neq 0, \alpha = 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \log \left( \frac{\lambda_i^\alpha (A) \lambda_{n-i+1}^{-\alpha} (B) }{1 + \log\left( \lambda_i^\alpha (A) \lambda_{n-i+1}^{-\alpha} (B) \right) } \right), & \text{if } \alpha = -\beta \neq 0, \\

\medskip
\displaystyle\frac{1}{2}\sum_{i = 1}^n \left( \log  \lambda_i (A) -\log \lambda_{n-i+1} (B)  \right)^2, &\text{if } \alpha = \beta = 0;
\end{cases}
\end{equation*}
and
\begin{equation*}
D_{\alpha, \beta}(A \| B) \ge
\begin{cases}
\medskip
\displaystyle\frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{i}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{i}^{\alpha} (B) }{\alpha + \beta} \right), &\text{if } \alpha \beta, \alpha + \beta\neq 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \left( \frac{\lambda_{i}^{\alpha} (B)}{\lambda_i^{\alpha} (A)}  - \log\left( \frac{\lambda_{i}^{\alpha} (B)}{\lambda_i^{\alpha} (A)} \right) -1 \right) , & \text{if } \alpha\neq 0, \beta = 0, \\

\medskip
\displaystyle\frac{1}{\beta^2} \sum_{i=1}^n \left( \frac{\lambda_{i}^{\beta} (A)}{\lambda_i^{\beta} (B)}  - \log \left( \frac{\lambda_{i}^{\beta} (A)}{\lambda_i^{\beta} (B)} \right) -1 \right), & \text{if } \beta\neq 0, \alpha = 0, \\

\medskip
\displaystyle\frac{1}{\alpha^2} \sum_{i=1}^n \log \left( \frac{\lambda_i^\alpha (A) \lambda_{i}^{-\alpha} (B) }{1 + \log\left( \lambda_i^\alpha (A) \lambda_{i}^{-\alpha} (B) \right) } \right), & \text{if } \alpha = -\beta \neq 0, \\

\medskip
\displaystyle\frac{1}{2}\sum_{i = 1}^n \left( \log  \lambda_i (A) -\log \lambda_i (B)  \right)^2, &\text{if } \alpha = \beta = 0.
\end{cases}
\end{equation*}
If $\alpha \beta < 0$, the inequalities for $D_{\alpha, \beta}(A \| B)$ in the case of $\alpha \beta, \alpha + \beta\neq 0$ are reversed.
\end{thm}

\begin{proof}
We start with the case of $\alpha \beta, \alpha + \beta\neq 0$. Consider the function $f: \mathbb{R}_{++} \ra \mathbb{R} $ defined by
\begin{equation*}
f(s) = \log \left( \frac{\alpha s^\beta + \beta s^{-\alpha}}{\alpha + \beta} \right),\quad  s>0.
\end{equation*}
We have that for any $s > 0$,
\begin{equation*}
s f' (s) = \frac{\alpha \beta (s^\beta - s^{-\alpha})}{\alpha s^\beta + \beta s^{-\alpha}}.
\end{equation*}
Then, for any $s > 0$,
\begin{equation*}
\left( s f' (s) \right)' = \frac{\alpha \beta (\alpha + \beta)^2 s^{\beta - \alpha - 1}}{(\alpha s^\beta + \beta s^{-\alpha})^2} =
\begin{cases}
> 0, &\text{if } \alpha\beta >0, \\
< 0, &\text{if } \alpha\beta <0.
\end{cases}
\end{equation*}
By Theorem~\ref{thm:matrix_rearrange}, if $\alpha \beta >0$, then
\begin{align*}
& \frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{i}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{i}^{\alpha} (B) }{\alpha + \beta} \right) \\
& \quad\le D_{\alpha, \beta}(A \| B) \le \frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{n-i+1}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{n-i+1}^{\alpha} (B) }{\alpha + \beta} \right) ;
\end{align*}
and if $\alpha \beta <0$, then
\begin{align*}
& \frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{i}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{i}^{\alpha} (B) }{\alpha + \beta} \right) \\
& \quad\ge D_{\alpha, \beta}(A \| B) \ge \frac{1}{\alpha \beta} \sum_{i=1}^n \log\left( \frac{ \alpha \lambda_i^\beta (A) \lambda_{n-i+1}^{-\beta} (B) + \beta \lambda_i^{-\alpha} (A) \lambda_{n-i+1}^{\alpha} (B) }{\alpha + \beta} \right) .
\end{align*}
For the case of $\alpha\neq 0$ and $\beta = 0$, we consider the function $f: \mathbb{R}_{++} \ra \mathbb{R} $ defined by
\begin{equation*}
f(s) = s^{-\alpha} + \alpha \log s   -1 ,\quad s > 0.
\end{equation*}
We have that for any $s > 0$,
\begin{equation*}
s f'(s) = \alpha (1 -s^{-\alpha}) .
\end{equation*}
Then, for any $s>0$,
\begin{equation*}
\left( s f' (s) \right)' = \alpha^2 s^{-\alpha - 1} > 0.
\end{equation*}
By Theorem~\ref{thm:matrix_rearrange},
\begin{align*}
& \frac{1}{\alpha^2} \sum_{i=1}^n \left( \frac{\lambda_{i}^{\alpha} (B)}{\lambda_i^{\alpha} (A)}  - \log \left( \frac{\lambda_{i}^{\alpha} (B)}{\lambda_i^{\alpha} (A)} \right) -1 \right) \\
& \quad\le D_{\alpha, \beta}(A \| B) \le \frac{1}{\alpha^2} \sum_{i=1}^n \left( \frac{\lambda_{n-i+1}^{\alpha} (B)}{\lambda_i^{\alpha} (A)}  - \log\left( \frac{\lambda_{n-i+1}^{\alpha} (B)}{\lambda_i^{\alpha} (A)} \right) -1 \right) .
\end{align*}
For the case of $\beta\neq 0$ and $\alpha = 0$, by using exactly the same argument as that for the case of $\alpha\neq 0$ and $\beta = 0$, we can prove that
\begin{align*}
& \frac{1}{\beta^2} \sum_{i=1}^n \left( \frac{\lambda_{i}^{\beta} (A)}{\lambda_i^{\beta} (B)}  - \log \left( \frac{\lambda_{i}^{\beta} (A)}{\lambda_i^{\beta} (B)} \right) -1 \right) \\
& \quad\le D_{\alpha, \beta}(A \| B) \le \frac{1}{\beta^2} \sum_{i=1}^n \left( \frac{\lambda_i^{\beta} (A)}{\lambda_{n-i+1}^{\beta} (B)}  - \log \left( \frac{\lambda_i^{\beta} (A)}{\lambda_{n-i+1}^{\beta} (B)} \right) -1 \right) .
\end{align*}
For the case of $\alpha = -\beta \neq 0$, we consider the function $f: \mathbb{R}_{++} \ra \mathbb{R} $ defined by
\begin{equation*}
f(s) = \log\left( \frac{s^{\alpha}}{1+ \alpha \log s} \right), \quad s > 0.
\end{equation*}
We have that for any $s > 0$,
\begin{equation*}
s f'(s) = \frac{\alpha^2 \log s}{1+\alpha \log s} .
\end{equation*}
Then, for any $s>0$,
\begin{equation*}
\left( s f' (s) \right)' = \frac{\alpha^2 }{s (1 + \alpha \log s)^2} > 0.
\end{equation*}
By Theorem~\ref{thm:matrix_rearrange},
\begin{align*}
& \frac{1}{\alpha^2} \sum_{i=1}^n \log \left( \frac{\lambda_i^\alpha (A) \lambda_{i}^{-\alpha} (B) }{1 + \log\left( \lambda_i^\alpha (A) \lambda_{i}^{-\alpha} (B) \right) } \right) \\
& \quad\le D_{\alpha, \beta}(A \| B) \le \frac{1}{\alpha^2} \sum_{i=1}^n \log \left( \frac{\lambda_i^\alpha (A) \lambda_{n-i+1}^{-\alpha} (B) }{1 + \log\left( \lambda_i^\alpha (A) \lambda_{n-i+1}^{-\alpha} (B) \right) } \right) .
\end{align*}
For the case of $\alpha = \beta = 0$, it is the same inequality as in Corollary~\ref{coro:R_dist}. This completes the proof.
\end{proof}

\section*{Acknowledgments}
The author is grateful to Cheuk Ting Li, Chi-Kwong Li, Wing-Kin Ma and Viet Anh Nguyen for their valuable comments on the manuscript.

\bibliographystyle{abbrv}
\bibliography{references}
\end{document}


TITLE: Divide matrix using left division
QUESTION [1 upvotes]: In matlab, I defined
a=[1;2;3]
b=[4;5;6]

both a and b are not square matrix.
and execute a\b will return 2.2857
From various sources, we understand that a\b ~= inv(a)*b, but in my case, a is not a square matrix, thus we can't perform an inverse operation on it.
I am actually translating matlab code to c#, and I need to know how do left division between non-square matrix calculated.
Thanks!

REPLY [1 votes]: In Matlab $a $\ $b =(a'a)^{-1}a'b$, i.e. $b$ is projected onto $a$.
A little bit more information: Consider,
$$
b \approx ax
$$
where $x$ is unknown and there are no exact solutions i.e. $b$ and $a$ have many rows and few columns, then the typical way to solve this problem is to solve for $x$ by projecting $b$ onto $a$ or by taking the point on the space $a$, which is closest to be i.e. $b \approx P_ab=a(a'a)^{-1}a'b=ax$.


TITLE: Expected sum of dropped intervals
QUESTION [0 upvotes]: For each $n\in\mathbb{N}$, let $I_n$ be an interval of length $1/2^{n}$. We drop each $I_n$ onto the interval $[0,1]$ uniformly at random (so that there's "wraparound" if need be). What is the expected length of the union of all the $I_n$'s?
I can see that it should be less than $3/4$, and greater than $5/8$, but can't get a precise number. In particular, if $a_k$ is the expected length of the union of the first $k$ intervals, then I believe we have $a_1 = 1/2$ and $$a_{n+1} = (1-a_n)\frac{1}{2^{n+1}} + a_n$$ But I can't figure out how to solve this recurrence and compute $\lim_{n\to\infty} a_n$.

REPLY [3 votes]: It appears that $2^{(n+2)(n+1)/2} a_{n+1} $ is in the OEIS as sequence A114604.  Unfortunately there's not much listed there about this sequence.


TITLE: Runge-Kutta method and step doubling
QUESTION [7 upvotes]: I am studying Runge-Kutta and step size control and came up with a few doubts. Because they are related with this integration method, I will divide it in two parts. First, allow me to introduce the problem.

$1^{st}$ part - questions about Runge-Kutta Method
Consider a $2^{nd}$ order Runge-Kutta with general form:
$k_{1}=hf(x_{n},y_{n})$
$k_{2}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{1})$
$y_{n+1}=y_{n}+k_{2}+O(h^{3})$
where $f(x_{n},y_{n}) = y'(x_{n})$
Now, if we are to consider $4^{th}$ order Runge-Kutta we would get
$k_{1}=hf(x_{n},y_{n})$
$k_{2}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{1})$
$k_{3}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{2})$
$k_{4}=hf(x_{n}+h,y_{n}+k_{3})$
$y_{n+1}=y_{n}+\frac{1}{6}k_{1}+\frac{1}{3}k_{2}+\frac{1}{3}k_{3}+\frac{1}{6}k_{4}+O(h^{5})$
This leads me to the following questions:

I understand why the 2nd order method has the $y_{n+1}$ indicated above. Yet, shouldn't the $4^{th}$ order version of the method be expressed only as $y_{n+1}=y_{n}+k_{4}+O(h^{5})$ given that $k_{4}$ implicitly has the values of $k_{1}$ to $k_{3}$?
Why does the $4^{th}$ order version have those fractional coefficients?

$2^{nd}$ part - questions about step-size control
Consider the exact solution for an advance from $x$ to $x+2h$ by $y(x+2h)$ and the two approximate solutions by $y_{1}$ (one step 2h) and $y_{2}$ (two steps each of size $h$). Considering the $4^{th}$ order method we have:
$y(x+2h)=y_{1}+(2h)^{5}\phi+O(h^{6})+...$
$y(x+2h)=y_{1}+2(h)^{5}\phi+O(h^{6})+...$
The difference between these estimates permits estimating the truncation error:
$\Delta=y_{2}-y_{1}$
Which we then use to improve the numerical estimate of the true solution:
$y(x+2h)=y_{2}+\frac{\Delta}{15}+O(h^{6})$
This brings me to the following questions:

In the two expressions of y(x+2h) at the top, does $\phi$ include the terms $k_{1}...k_{4}$ in the first part of this post?
Why is the final expression $5^{th}$ order, if the original problem was $4^{th}$ order?
Where does the coefficient $\frac{1}{15}$ come from?

Thank you for all the insight!

REPLY [2 votes]: For the first part, the Wikipedia article http://en.m.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods has a detailed discussion of the different members of the family along with a derivation of RK-4. The key idea is that you can do whatever you want in terms of writing down the form of your approximation; all that matters is that doing a Taylor expansion makes all the error terms up to the order of approximation vanish. This is how the coefficients are chosen.
Then in the next part, $\phi$ is the the expression for the error made in the step, without the $(2h)^5$ term. It should be thought of as an expression in terms of the derivatives of $y$ at $x$, but its exact form isn't important, just its independence from $h$. It's the same in both lines to first order in $h$ so the errors are hidden away in the correction term. Note that fourth order means the error term is $h^5$ per step which it is throughout. You then use two fourth order approximations to get a better one by calculating the error approximately. This is reasonable since you've used more data.

As to the $1/15$ factor, that simply arises because $(2h)^5-2(h)^5=(16-1)h^5=15h^5$ and if you make only a step of size $h$ you get a factor of $h^5$. Try carefully defining and writing down the different things you work out, then you can see why you take the difference in this way.


text:
\section{Proof of lower bounds}\label{sec:lb-proof}

In what follows, we break Theorem~\ref{thm:lb} into two parts,
one for the linear convergence lower bound~\eqref{eq:cr-lb-lin} and one for
the sublinear lower bounds~\eqref{eq:cr-lb-sub-ncvx}
and~\eqref{eq:cr-lb-sub-cvx}. We restate each sub-theorem in a way that
clearly shows our control over problem-dependent parameters when
constructing the hard problem instances. In our proofs we will make use of
the following expression for the optimality gap in the cubic-regularization
problem,
\begin{equation}\label{eq:fx-s-expression}
\fcu\left(x\right)-\fcu\left(\scu\right)=
\frac{1}{2}(x-\scu)^T\Acu (x-\scu)
+\frac{\rho}{6}\left(\| \scu\| -\| x\| \right)^{2}\left(\| \scu\| +2\| x\|
\right),
\end{equation}
where $\Acu = A + \rs I$.

\subsection{Proof of linear convergence lower bound}

\begin{customthm}{\ref{thm:lb}, part I}
	Let $\lmin, \lmax, \ltr, \Delta \in \R$ such that $\lmin \le \lmax$, $\ltr
	> \max\{-\min,0\}$ and $R, \Delta>0$. For every $t \ge 1$ and every
	$d>t$ there exists $A\in\R^{d\times d}$, $b\in\R^d$ and $\rho > 0$
	such that
	\begin{itemize}
		\item all eigenvalues of $A$ are in $[\lmin, \lmax]$,
		\item the solution $\scu = \argmin_{x\in\R^d}\fcu(x)$
		satisfies

		$\rs = \ltr$,
		\item $\fcu(0) - \fcu(\scu) = \Delta$, and
	\end{itemize}
	\begin{equation*}
	\fcu(s) - \fcu(\scu) >

	\left(1+\frac{\rs}{3(\rs + \lmin)} \right)^{-1}
	\left[\fcu(0) - \fcu(\scu) \right]
	\exp\left\{
	-\frac{4t}{\sqrt{\frac{\rs + \lmax}{\rs +\lmin}}-1}
	\right\}.
	\end{equation*}
	for every $s\in\Krylov$.
\end{customthm}

\begin{proof}
	From Lemma~\ref{lem:cheby-first} with $\alpha = \ltr + \lmin$,
	$\beta = \ltr + \lmax$ and $n=t$, we have that there exist $\xi_0,
	\ldots,
	\xi_t \in [\alpha, \beta]$ and probability distribution $\pi_0, \ldots,
	\pi_{t}$ such that
	\begin{equation*}
	\min_{p \in \Polys[t]} \sum_{k=0}^{t} \pi_k (1-\xi_k p(\xi_k))^2 \ge
	e^{-4t/(\sqrt{\kappa}-1)},
	\end{equation*}
	where $\kappa = \beta/\alpha = (\lmax+\ltr)/(\lmin+\ltr)$. We let $\xi$
	and $\sqrt{\pi}$ denote vectors with entries $\xi_0, \ldots, \xi_{t}$ and
	$\sqrt{\pi_0}, \ldots, \sqrt{\pi_t}$ respectively.

	To construct the problem instance $(A,b,\rho)$ we assume without loss
	of generality $d=t+1$, as higher dimensional instances can be obtained
	by zero-padding a $(t+1)$-dimensional construction. We set
	\begin{equation*}
	A = \diag( \xi - \ltr )
	,~
	b = \mu \Atr^{1/2}\sqrt{\pi}
	~\mbox{and}~
	\rho =\ltr/ \norm{\Atr^{-1}b},
	\end{equation*}
	where we will choose $\mu > 0$ to set the value of
	$\fcu(0)-\fcu(\scu)$.
	First, we note that for any value of $\mu$ our choice of $\rho$
	guarantees that  $\norm{\Atr^{-1}b} = \ltr/\rho$, making $\scu =
	-\Atr^{-1}b$ the unique global minimizer of $\fcu$. We therefore have
	by equation~\eqref{eq:fx-s-expression}
	\begin{equation*}
	\fcu(0)-\fcu(\scu) = \half \scu^T \Atr \scu + \frac{\rs}{6}\norm{\scu}^2
	= \frac{\mu^2}{2}\left( 1 + \frac{\ltr}{3} \sqrt{\pi}^T \Atr^{-1}
	\sqrt{\pi} \right),
	\end{equation*}
	so for every $\Delta > 0$ there is $\mu$ for which $\fcu(0)-\fcu(\scu) =
	\Delta$. Noting that $\sqrt{\pi}^T \Atr^{-1} \sqrt{\pi} \le (\ltr +
	\lmin)^{-1}\norm{\sqrt{\pi}}^2 = (\ltr + \lmin)^{-1}$, we also have
	\begin{equation*}
	\frac{\mu^2}{2} \ge \Delta \left(1+\frac{\ltr}{3(\ltr + \lmin)} \right)^{-1} .
	\end{equation*}

	Now, every $s\in\Krylov$ is of the form $s=-p(\Atr)b$ for
	$p\in\Polys[t]$, and using
	equation~\eqref{eq:fx-s-expression} again we have
	\begin{align*}
	\fcu(s)-\fcu(\scu) &\ge \half \norm{\Atr^{1/2}(s-\scu)}^2
	\stackrel{(a)}{=} \half\norm{(I-\Atr p(\Atr))\Atr^{-1/2}b}^2 \\ &
	\stackrel{(b)}{=} \frac{\mu^2}{2}\sum_{k=0}^{n} \pi_k (1-\xi_k
	p(\xi_k))^2
	\stackrel{(c)}{\ge}
	\frac{\mu^2}{2} e^{-4t/(\sqrt{\kappa}-1)},
	\end{align*}
	where in $(a)$ we substituted $s=-p(\Atr)b$ and $\scu=-\Atr^{-1}b$, in
	$(b)$ we used our construction of $A$ and $b$, and in $(c)$ we used the
	guarantee from Lemma~\ref{lem:cheby-first}. The result follows from
	substituting our lower bound on $\mu^2$ and recalling that $\ltr = \rs$.
\end{proof}

\subsection{A lower bound for finding eigenvectors}
The ``non-convex'' lower bound is in its heart a statement about the
difficulty of approximating an extremal eigenvector in a Krylov subspace,
which we state explicitly here. The proof of the lemma consists of applying
``in reverse'' the same polynomial approximation result
(Lemma~\ref{lem:cheby-second}) that~\citet{KuczynskiWo92} use for
proving upper bounds on finding eigenvector with the Lanczos method
(which we state as Lemma~\ref{lem:eigenvec-tight}).

\begin{restatable}[Finding
	eigenvectors: lower bound]{lemma}{lemEigenLB}\label{lem:eigenvec-lb}
	For every $d>0$, vector $v\in \R^d$, unit vector $u\in\R^d$ and $t<d$,
	there exists matrix
	$M\in\R^{d\times d}$ such that $M \succeq 0$, $M u = 0$, and for
	every $z \in \Krylov[t][M,v]$,
	\begin{equation*}
	\frac{z_t^T M z_t}{\opnorm{M}\norm{z_t}^2} \ge
	\min\left\{\frac{1}{4},
	\frac{1}{64(t-\half)^2}
	\log^2\left(-3+4\frac{\norm{v}^2}{(u^T v)^2}\right)\right\}.
	\end{equation*}
\end{restatable}

\begin{proof}
	We take $\opnorm{M}=1$ without loss of generality; results for arbitrary
	norms of $M$ follow by scaling the construction below. Define
	\begin{equation}\label{eq:eigenvec-lb-err-def}
	\err \defeq
	\min\left\{\frac{1}{4},
	\frac{1}{64(t-\half)^2}
	\log^2\left(-3+4\frac{\norm{v}^2}{(u^T v)^2}\right)\right\}.
	\end{equation}

	We apply Lemma~\ref{lem:cheby-second} with $n=t-1$, $\alpha = \err$
	and $\beta=1$, to obtain $\xi_1, \ldots, \xi_t \in [\err, 1]$ and
	probability
	distribution $\pi_1, \ldots, \pi_t$ such that
	\begin{equation}\label{eq:cheby-second-lb-applied}
	\min_{p \in \Polys[t-1]} \sum_{k=1}^{t} \pi_k (\xi_k - \err)(1-\xi_k
	p(\xi_k))^2
	\ge  \frac{4\err}{e^{2(2t-1)/(\frac{1}{\sqrt{\err}}-1)}-1}.
	\end{equation}

	We assume without loss of generality that $d=t+1$ (otherwise we
	zero-pad), and construct $M$ as follows. First, we take the eigenvalues
	of
	$M$
	to be $0, \xi_1, \ldots, \xi_t$, satisfying $0\preceq M \preceq I$. Next,
	we
	let $u$ be the eigenvector of $M$
	corresponding to eigenvalue $0$, satisfying $Mu=0$. Finally, for
	$i=1,\ldots, t$ we choose the
	eigenvector $u_i$ corresponding to eigenvalue $\xi_i$ such that $(u_i^T
	v)^2 = \pi_i (\norm{v}^2 - (u^T v)^2)$.

	Assume by contradiction
	\begin{equation}\label{eq:eigenvec-lb-contra-assumption}
	\min_{z\in\Krylov[t][M,v]} \frac{ z^T M z
	}{\norm{z}^2 } < \err,
	\end{equation}
	and let $q\in \Polys[t]$ be be such that
	\begin{equation*}
	\frac{ \sum_{i=1}^t \xi_i q^2(\xi_i) (u_i^T v)^2}
	{ q^2(0)(u^T v)^2 + \sum_{i=1}^t q^2(\xi_i) (u_i^T v)^2}
	= \frac{ (q(M)v)^T M q(M)v
	}{\norm{q(M)v}^2 }

	= \min_{z\in\Krylov[t][M,v]} \frac{ z^T M z
	}{\norm{z}^2 } < \err.
	\end{equation*}
	Rearranging, using $(u_i^T
	v)^2 = \pi_i (\norm{v}^2 - (u^T v)^2)$, and letting $\tilde{q}(x) =
	q(x)/q(0)$,
	we have that
	\begin{equation*}
	\err  > \left( \frac{\norm{v}^2}{(u^T v)^2} - 1\right)
	\sum_{i=1}^{t} \pi_i (\xi_i - \err) \tilde{q}^2(\xi_i)
	\ge
	\left( \frac{\norm{v}^2}{(u^T v)^2} - 1\right) \frac{4
		\err}{e^{2(2t-1)/(\frac{1}{\sqrt{\err}}-1)}-1}.
	\end{equation*}
	where in the last transition we used that $\tilde{q}(0)=1$ and therefore it
	is
	of the form $1-xp(x)$ for some $p\in\Polys[t-1]$, so the lower
	bound~\eqref{eq:cheby-second-lb-applied} applies. Rearranging gives
	\begin{equation*}
	\err > h\left(\frac{1}{16(t-\half)^2}
	\log^2\left(-3+4\frac{\norm{v}^2}{(u^T v)^2}\right)\right)
	,~~
	h(x) = \frac{x}{(1+\sqrt{x})^2}.
	\end{equation*}
	Using $h(x) \ge \frac{1}{4}\min\{1, x\}$ and the
	definition~\eqref{eq:eigenvec-lb-err-def} of $\err$, we see that the
	above
	bound
	gives the contradiction  $\err > \err$ and therefore
	assumption~\eqref{eq:eigenvec-lb-contra-assumption} must be false
	and
	we have the desired result $\min_{z\in\Krylov[t][M,v]} \frac{ z^T M z
	}{\norm{z}^2 } \ge \err$.
\end{proof}

\subsection{Proof of sublinear convergence lower bound}

\begin{customthm}{\ref{thm:lb}, part II}
	Let $\lmin, \lmax, R, \tau \in \R$ such that $\lmin\le\lmax$, $\tau \ge
	1$
	and $R>0$. For
	every $t \ge 1$ and every
	$d>t$ there exists $A\in\R^{d\times d}$, $b\in\R^d$ and $\rho > 0$
	such that
	\begin{itemize}
		\item all eigenvalues of $A$ are in $[\lmin, \lmax]$,
		\item the solution $\scu = \argmin_{x\in\R^d}\fcu(x)$
		satisfies $\norm{\scu} = R$,

		\item there exists unit eigenvector $u_{\min}$ such that $u_{\min}^T
		A u_{\min} = \lmin$ and $\frac{\norm{b}}{|u_{\min}^T b|} = \tau$, and
	\end{itemize}
	\begin{equation*}
	\fcu(s) - \fcu(\scu) >
	\min\left\{
	\lmax^{-}-\lmin~,~
	\frac{\lmax-\lmin}{16(t-\half)^2}
	\log^2\left(\frac{\norm{b}^2}{( u_{\min}^T b)^2}\right)
	\right\}\frac{\norm{\scu}^2}{32},
	\end{equation*}
	where $\lmax^{-}=\min\{\lmax,0\}$, and
	\begin{equation*}
	\fcu(s) - \fcu(\scu) >
	\frac{(\lmax - \lmin)\norm{\scu}^2}{16(t+\half)^2}.
	\end{equation*}
	for every $s\in\Krylov$.
\end{customthm}

\renewcommand{\err}[1][t]{\epsilon_{#1}}

\begin{proof}
	We begin with the first, ``non-convex'' bound, which is essentially a
	reduction to the eigenvector problem. Here we assume $\lmin \le 0$ as
	otherwise the lower bound is vacuous. We use
	Lemma~\ref{lem:eigenvec-lb} to construct $M\in\R^{d\times d}$
	and unit vectors $u_{\min}, v \in R^d$ such that $M\succeq 0$,
	$\opnorm{M}=\lmax - \lmin$, $M u_{\min} = 0$, $\norm{v}/|u_{\min}^T
	v|
	= \tau$ and for every $z\in \Krylov[t][M,v]$
	\begin{align}\label{eq:cr-sub-lb-err-def}
	\frac{z^T M z}{\norm{z}^2} & \ge \frac{\lmax - \lmin}{4}
	\min\left\{1 \,,\,
	\frac{1}{16(t-\half)^2}
	\log^2\left(-3+4\frac{\norm{v}^2}{( u_{\min}^T v)^2}\right)\right\}
	\nonumber \\ &
	\ge
	\frac{1}{4}\min\left\{\lmax^{-} -\lmin \,,\,
	\frac{\lmax - \lmin}{16(t-\half)^2}
	\log^2\left(\frac{\norm{v}^2}{( u_{\min}^T v)^2}\right)\right\}
	\defeq
	\err,
	\end{align}
	where $\lmax^{-}=\min\{\lmax,0\}$.
	We let $\eps > 0$ be a parameter to be specified later. We let
	\begin{equation*}
	\ltr = -\lmin + \eps
	\end{equation*}
	and construct the cubic regularization instance as follows
	\begin{equation*}
	A = M + \lmin I
	~,~
	b = \frac{R}{\norm{\Atr^{-1}v}}v
	~,~
	\rho = \ltr / R.
	\end{equation*}
	The solution for this instance is unique and satisfies $\scu =
	-\Atr^{-1}b =
	- R \Atr^{-1}v / \norm{\Atr^{-1}v}$ so that $\norm{\scu} = R$, and
	moreover we note that $\norm{b} \to 0$ as $\eps\to 0$. For every
	$s\in\Krylov[t][M,v]=\Krylov[t][A,b]$,
	\begin{equation*}
	\fcu(s) = \half s^T A s + b^T s + \frac{\rho}{3}\norm{s}^3
	\ge -\norm{b}\norm{s} + \half(\lmin + \err)\norm{s}^2 +
	\frac{\rho}{3}\norm{s}^3.
	\end{equation*}
	The RHS above is minimal for
	\begin{equation*}
	\norm{s} = \tilde{R} \defeq -\frac{\lmin + \err}{2\rho} +
	\sqrt{\left( \frac{\lmin + \err}{2\rho} \right)^2 + \frac{\norm{b}}{\rho}}
	\le \frac{-\lmin - \err}{\rho}+
	\sqrt{\frac{\norm{b}}{\rho}},
	\end{equation*}
	where the bound holds since our definition of $\err$ implies $\err \le
	-\lmin$ and so $-\lmin-\err \ge 0$.
	The minimum value of the RHS satisfies
	\begin{equation}\label{eq:cr-sub-lb-kryl-lb}
	\fcu(s) \ge -\frac{2}{3}\norm{b}\tilde{R} - \frac{1}{6}(-\lmin - \err)
	\tilde{R}^2.

	\end{equation}
	Taking without loss of generality $u_{\min}^T b \le 0$ and using $\rho
	=
	\ltr / R$, and $\ltr = -\lmin + \eps$, we have
	\begin{equation}\label{eq:cr-sub-lb-opt-lb}
	\fcu(\scu) \le \fcu(R \cdot u_{\min}) \le \half \lmin R^2 + \frac{1}{3}\ltr
	R^2
	= \frac{1}{6} \lmin R^2 + \frac{\eps}{3} R^2.
	\end{equation}

	Recall that $\norm{b}\to
	0$
	as $\eps\to0$, and take $\eps>0$
	sufficiently small so that
	\begin{equation*}
	\eps < \err/24
	~~
	\mbox{and}
	~~
	\norm{b} \le \min\{\err R/24 , \err^2/\rho \},
	\end{equation*}
	which implies also
	\begin{equation*}
	\tilde{R} \le \frac{-\lmin - \err}{\rho}
	+ \frac{\err}{\rho} = \frac{-\lmin}{\rho} \le \frac{\ltr}{\rho} = R.
	\end{equation*}
	Using $\tilde{R}\le R$, we may replace $\tilde R$ with $R$ in the
	bound~\eqref{eq:cr-sub-lb-kryl-lb}, and combining this
	with~\eqref{eq:cr-sub-lb-opt-lb} and the bounds on $\norm{b}$ and
	$\eps$ we obtain
	\begin{equation*}
	\fcu(s)-\fcu(\scu) \ge

	\frac{\err}{6}R^2 - \frac{2\norm{b}}{3}R -
	\frac{\eps}{3}R^2 \ge \frac{\err}{8} R^2.
	\end{equation*}
	Recalling $\norm{\scu} = R$ and the
	definition~\eqref{eq:cr-sub-lb-err-def}
	of $\err$, we get the desired ``non-convex'' lower bound.

	To derive the alternative, ``convex'' lower bound,
	we again let
	$0<\eps<\lmax-\lmin$ be a parameter to be determined, and we apply
	Lemma~\ref{lem:cheby-second} with $n=t$, $\alpha=\eps$,
	$\beta=\lmax-\lmin$ to obtain points $\xi_0, \ldots, \xi_t \in [0,
	\lmax-\lmin]$ and probability masses $\pi_0, \ldots, \pi_t$ such that
	\begin{equation*}
	\min_{p \in \Polys} \sum_{k=0}^{n} \pi_k (\xi_k - \eps)(1-\xi_k
	p(\xi_k))^2 = \left[\minmaxU[t][\frac{\lmax-\lmin}{\eps}] \right]^2.
	\end{equation*}
	To construct the hard instance we again set
	\begin{equation*}
	\ltr = -\lmin + \eps.
	\end{equation*}
	Letting $\xi$ and $\sqrt{\pi}$ denote vectors with entries $\xi_i$ and
	$\sqrt{\pi}_i$, we set
	\begin{equation*}
	A = \diag(\xi - \ltr)
	~,~
	b = R\cdot\Atr\sqrt{\pi}
	~,~
	\rho = \ltr / R.
	\end{equation*}
	Again we have that $\scu = -\Atr^{-1}b$ is the unique solution and
	$\norm{\scu} = R\norm{\sqrt{\pi}}=R$. Let $s\in\Krylov$, then
	\begin{equation*}
	s = -p(\Atr)b = p(\Atr)\Atr \scu = -R p(\Atr)\Atr \sqrt{\pi}
	\end{equation*}
	for some $p\in\Polys[t]$. By equality~\eqref{eq:fx-s-expression} we
	have
	\begin{align*}
	\fcu(s) - \fcu(\scu) & \ge \frac{1}{2}\norm{\Atr^{1/2}(s-\scu)}^2
	=
	\frac{R^2}{2}
	\sum_{k=0}^t \pi_k \xi_k (1-\xi_k p(\xi_k) )^2 \\ &
	\ge \frac{R^2}{2} \sum_{k=0}^t \pi_k (\xi_k -\eps) (1-\xi_k p(\xi_k) )^2
	= \frac{R^2}{2}  \left[\minmaxU[t][\frac{\lmax-\lmin}{\eps}] \right]^2.
	\end{align*}
	Note that
	\begin{equation*}
	\lim_{\eps\to 0} \minmaxU[t][\frac{\lmax-\lmin}{\eps}]
	=
	\frac{\sqrt{\lmax-\lmin}}{2t+1}.
	\end{equation*}
	Therefore, we can choose $\eps$ sufficiently small so that
	\begin{equation*}
	\left[\minmaxU[t][\frac{\lmax-\lmin}{\eps}] \right]^2
	\ge \frac{\lmax-\lmin}{2(2t+1)^2},
	\end{equation*}
	which gives the proof for the ``convex'' lower bound, as
	$\norm{\scu}=R$.
\end{proof}

config: arxiv


TITLE: Meaning of the uniform ensemble
QUESTION [0 upvotes]: In statistical physics (and viewing this from a classical point of view) for an isolated system we can say that a system will have an energy constant in time.
People define the following uniform probability distribution of microstates ($P$), which is also called the uniform ensemble:
$P=0$ if  $H(q,p)> E$ and $P\neq 0$ if $H(q,p)< E$, where $H$ is the hamiltonian of a system.
But the hamiltonian of a system is also equal to the energy of a system, so how can we say that there is a probability of, in a given system, there being a microstate, a point $(q,p)$, where the hamiltonian is less than the energy of the system; to me this probability distribution function makes no sense.
Also I don't understand the reasoning behind creating it, it just seems to come out of nowhere, but am I correct in saying that the only point of having this distribution is that from this probability density, we can find that its density is concentrated at the surface of the equienergetic surface in phase-space, which allow us to define a function of the density of the microstates $(q,p)$, which in turn allows us to find the expected values of observables?

REPLY [0 votes]: Firstly, it is probably worth referring to this previous question and answer for some background information and defining equations, while making clear that your question is different from that one.
In general terms, I agree with you. The uniform ensemble, in which all states having an energy less than the prescribed value $E$ are equally weighted, does not have a simple physical interpretation. I don't agree with you that there is some kind of inconsistency here: $E$ is just the maximum possible energy, and some other symbol such as $H(q,p)$ represents the energy for given $q$ and $p$.
The ensemble has a small advantage: that the entropy formula $S=k_B\ln \overline{\Omega}$ involves taking the logarithm of a dimensionless quantity $\overline{\Omega}$, which we can interpret as the number of states having energy less than $E$ (once we have normalized the integrals over $q$ and $p$ with the appropriate factor of Planck's constant $h$).
For the microcanonical ensemble, one must remember that the energy shell formally has an arbitrary width $\Delta E$, so that $S=k_B\ln \Omega$ refers to the number of states with energy between $E$ and $E+\Delta E$. Then it is necessary to discuss how (for a large enough system) the choice of $\Delta E$ does not practically affect the calculation of thermodynamic properties, starting with $S$. Often, though, this is forgotten, and we just write $S=k_B\ln \Omega$, where $\Omega$ is a density of states (per unit energy); we shouldn't really do this, as $\Omega$ defined this way is not dimensionless. This isn't a serious deficiency, as long as it is borne in mind. Of course, the microcanonical ensemble is physically more appealing, corresponding in principle to an isolated system.
For the uniform ensemble, as you imply in your question, the $\Delta E$ arises "naturally" from the very rapid increase of $\Omega(E)$ with $E$, causing most of the states included in $\overline{\Omega}(E)$ to be concentrated near $E$.
All ensembles are artificial constructs, to an extent.
If you are saying that the uniform ensemble is more artificial than some of the others, then yes, I think you are right.