Let $A$ be a fixed $n$ by $n$ real symmetric positive definite matrix with eigenvalues $\lambda\_1 \ge \lambda\_2 \ge \ldots \ge \lambda\_n > 0$, and let $f(A):=\sum\_{i=1}^n\log\lambda\_i$, and let $X$ be a random $n$ by $k$ matrix with real iid copies distributed according to $N(0,\sigma^2/k)$.


The regime
----------


* $n$ is fixed (in particular, $n \not \to \infty$).
* $k \to \infty$ (in particular, $k \gg n$).


Question
--------


* How close is $f(A+XX^T)$ to $f(A)$ in espectation ?
* What is an upper-bound for $\mathbb P(|f(A+XX^T)-f(A)| > \epsilon)$?


Observations
============


I've observed that $f(A+XX^T)$ is approximately $\mathcal N(\mu,s^2)$, for some $\mu \in \mathbb R$, and $s > 0$.


Back-of-envelop calculation
---------------------------


By triangle inequality, one has
$$
\begin{split}
|f(A+XX^T) - f(A)| \le &|f(A+\sigma^2 I\_n) - f(A)|\\
&\quad + |f(A+XX^T) - f(A+\sigma^2 I\_n)|.
\end{split}
\tag{\*}
$$


Note that as $k\rightarrow \infty$, $XX^T \rightarrow \sigma^2 I\_n$ in probability. Thus, by the delta method, we know that $f(A+XX^T) - f(A+\sigma^2 I\_n) \longrightarrow \mathcal N(0,s^2/k)$, where
$$
s^2 := n\sigma^4\|(A+\sigma^2 I\_n)^{-1}\|\_F^2 \le \sigma^4(\sum\_{j=1}^n\lambda\_j((A + \sigma^2)^{-1})^2 \le (\sqrt{n}\sigma^2\eta(A))^2,
$$
where
$$
\begin{split}
\eta(A) &= \eta(A; \sigma^2) := \text{trace}(A+\sigma^2 I\_n)^{-1} = \sum\_{i=1}^n(\lambda\_i(A)+\sigma^2)^{-1}
\le n\min(\sigma^{-2},\lambda\_n(A)^{-1}).
\end{split}
$$


On the other hand,
$$
|f(A + \sigma^2 I\_n) - f(A)| = \sum\_{i=1}^n\log(1 + \sigma^2/\lambda\_i) \le \sigma^2\sum\_{i=1}^n(\lambda\_i(A)+\sigma^2)^{-1} = \sigma^2\eta(A).
$$


Putting everything together then gives


$$
\begin{split}
E\_X|f(A+XX^T) - f(A)| &\le \sigma^2\frac{n}{\lambda\_n} + E\_X|f(A+XX^T)-f(A+\sigma^2 I\_n)|\\
&\le \sigma^2\eta(A) + \sqrt{\frac{n}{k}} \sigma^2 \eta(A) \to \sigma^2\eta(A).
\end{split},
$$


Thus it appears that,



> 
> To have $E|f(A+XX^T) - f(A)|$ small, it is sufficient to have $\sigma^2 \eta(A) \ll 1$ and $k \rightarrow \infty$.
> 
> 
> 


This doesn't solve my problem, but it raises suspicion to what the important problem parameters could be; here, $\sigma$, $k$, and $\eta(A)$ (or $n/\lambda\_n$, for an even cruder analysis).



Upper bound for $\mathbb P(|f(A+XX^T)-f(A)| > \epsilon)$, where $A$ is a fixed pd matrix and $X$ has random iid entries
Below, I provide a "high-probability" **non-asymptotic** bound (see (+) below) based on [non-linear Berry-Esseen theory](https://arxiv.org/pdf/0906.0177v2.pdf) developed by Iosif Pinelis. I'd be grateful if someone would kindly check that I didn't screw up anything. Thanks in advance!




---


Main tool: non-linear Berry-Esseen theory
-----------------------------------------


Let $ \mathcal H$ be a (possibly infinite-dimensional) Hilbert space with topological dual $\mathcal H^\*$, and let $g:\mathcal H \rightarrow \mathbb R$ be a function such that


* $g(0)=0$,
* $g$ has linear approximant $L \in \mathcal H^\*$ valid on a nonzero neighborhood of the origin, i.e there exist $\epsilon > 0,M>0$ such that


$$
|g(z) - L(z)| \le \frac{M}{2}\|z\|^2,\;\forall \|z\| \le \epsilon. \tag{1}
$$


Note that under such conditions, we automatically have that $g$ is (Fréchet) differentable at $0$ and $L=\nabla g(0)$.


Let $Z$ be a random vector on $\mathcal H$ such that $E Z = 0$ (i.e $Z$ is centered) and suppose $\tilde{\sigma} := \|L(Z)\|\_{Z,2} := (E\_Z|L(Z)|^2)^{1/2} < \infty$. The quantity $\tilde{\sigma}^2/k$ will play the role of a "proxy variance" for the random variable $g(Z)$. Finally, let $Z\_1,\ldots,Z\_k$ be iid copies of $Z$ and set $\overline{V} := (1/k)\sum\_{i=1}^kZ\_i$.



> 
> **Theorem (Corollary 3.7 of [reference paper](https://arxiv.org/pdf/0906.0177v2.pdf)).** *Let $p \in (2,3]$ such that $\|Z\|\_{Z,p} := (E\_Z\|Z\|\_p)^{1/p} < \infty$. Then
> $$
> \sup\_{t \in \mathbb R}\left|\mathbb P\left(\frac{g(\overline{V})}{\tilde{\sigma}/\sqrt{k}}\ge t\right)-\Phi(t)\right| \le Ck^{1-p/2},
> $$
> where $C$ is a constant which only depends on the distribution of $Z$ (in particular, $C$ is independent of the sample size $k$ and $p$).*
> 
> 
> 


Application: our problem
------------------------


For our own business, we let


* $\mathcal H$ be the euclidean space of $n$ by $n$ matrices equipped with the Frobenius trace inner product $\langle B,\tilde{B}\rangle\_{Fro} := \text{trace}(B^T\tilde{B})$. We denote induced norm by $\|B\|\_{Fro} := \langle B,B\rangle\_{Fro}^{1/2}$. Note that this space is nothing but euclidean $\mathbb R^{n^2}$ in disguise.
* Define
$$g(B) := \begin{cases}f(B + A + \sigma^2 I\_n) - f(A+\sigma^2 I\_n),&\mbox{ if }B + A + \sigma^2 I\_n \succ 0,\\0,&\mbox{ else.}\end{cases}
$$
where $f(B) := \sum\_{j=1}^n\log\lambda\_j(B)$.
* It's not hard to see that $g$ is differentiable at $0$ with derivative $L:=g'(0) := (A+\sigma^2 I\_n)^{-1}$. Moreover, $g$ has Lipschitz continuous gradient at $0$ and and so (1) is satisfied.
* For our random vector, we take $Z = RR^T-\sigma^2 I\_n$, where $R \in \mathbb R^n$ is a random vector with iid entries from $N(0,\sigma^2 I\_n)$. Thus $XX^T-\sigma^2 I\_n = (1/k)\sum\_{i=1}^k Z\_j =: \overline{V}$, where $Z\_j = X\_jX\_j^T$ are iid copies of $Z$ (where $X\_i$ is the $i$th column of the random $n$ by $k$ matrix $X$ in our original problem). Of course, $\|Z\|\_{Z,p} < \infty$ for all $p$ (Gaussians have finite moments).
* By Cauchy-Schwarz inequality, one computes
$$
\begin{split}
\tilde{\sigma}^2 &= \|L(Z)\|\_Z = \|L\|\_{Fro}^2\|Z\|\_{Z,2}^2 = \text{trace}((A+\sigma^2 I\_n)^{-2})E\_Z\|Z\|\_2^2\\
& \le (\sum\_{j=1}^n(\lambda\_j(A) + \sigma^2)^{-1})^2\cdot n \sigma^4 \le n\sigma^4\eta(A)^2 = (\sqrt{n}\sigma^2\eta(A))^2,
\end{split}
$$
where
$$
\begin{split}
\eta(A) &= \eta(A; \sigma^2) := \text{trace}(A+\sigma^2 I\_n)^{-1} = \sum\_{i=1}^n(\lambda\_i(A)+\sigma^2)^{-1}
\le n\min(\sigma^{-2},\lambda\_n(A)^{-1}).
\end{split}
$$


Putting everything together, and applying the above theorem, we obtain that for every $t \ge 0$, w.p at least $\Phi(t\sqrt{k})+\mathcal O(k^{-1/2})$,


$$
|f(A+XX^T) - f(A + \sigma^2 I\_n)| = |f(\overline{V}+A+\sigma^2 I\_n) - f(A + \sigma^2 I\_n)| \le t\sqrt{n}\sigma^2\eta(A).
$$


Combining with (\*) then gives: for all $t \ge 0$, it holds w.p at least $\Phi(t\sqrt{k/n})+\mathcal O(k^{-1/2})$ that


$$
|f(A+XX^T) - f(A)| \le \sigma^2\eta(A) + t\sigma^2\eta(A) = (1+t)\sigma^2\eta(A). \tag{+}
$$




---


Edit: Improved non-asymptotic bound for the term $|f(A+XX^T)-f(A+\sigma^2 I\_n)|$
=================================================================================



> 
> *It has been noted in the comments section of the question that Berry-Esseen sounds like an over-kill (and might produce sub-optimal bounds for my particular problem in which everything is sub-Gaussian...). To remedy this, I'll use well-known concentration results for estimation of covariance matrices, and then Weyl's inequality. Interestingly, just as in the Berry-Esseen method above, the key requirement is that the entries of $X$ be iid with finite moments of order $2 + \epsilon$.*
> 
> 
> 


By **Proposition 2.1** of [HOW CLOSE IS THE SAMPLE COVARIANCE MATRIX TO
THE ACTUAL COVARIANCE MATRIX?](https://www.math.uci.edu/%7Ervershyn/papers/sample-covariance.pdf), we know that for any $t \ge 0$, it holds with probability $1-2e^{-ct^2}$ that


$$
\|XX^T-\sigma^2I\| = \left\|\frac{1}{k}\sum\_{j=1}^kR\_iR\_i^T-\sigma^2 I\_n\right\| \le t\sigma^2\sqrt{\frac{n}{k}}.
$$


Thus by *Weyl's inequality*, it holds with probability $1-2e^{-ckt^2/n}$ that


$$
\max\_{1 \le i \le n} |\lambda\_i(A+XX^T)-\lambda\_i(A+\sigma^2)| \le \|XX^T-\sigma^2I\_n\| = \left\|\frac{1}{k}\sum\_{j=1}^kR\_iR\_i^T-\sigma^2 I\_n\right\| \le t\sigma^2,
$$
and so by the triangle inequality, it holds with probability $1-2e^{-ckt^2/n}$ that


$$
\begin{split}
|f(A+XX^T)-f(A+\sigma^2 I\_n)| &= \left| \sum\_{i=1}^n \log\left(\frac{\lambda\_i(A+XX^T)}{\lambda\_i(A + \sigma^2 I\_n)}\right)\right|\\
& \le \sum\_{i=1}^n \left|\log\left(\frac{\lambda\_i(A+XX^T)}{\lambda\_i(A + \sigma^2 I\_n)}\right)\right| \\
& \le \sum\_{i=1}^n\log\left(1 + \frac{t\sigma^2}{\lambda\_i(A)+\sigma^2}\right)
\\
&\le t\sigma^2\sum\_{i=1}^n (\lambda\_i(A)+\sigma^2)^{-1}\\
&= t\sigma^2\eta(A).
\end{split}
$$


