Fundamental limits of low-rank matrix estimation: the non-symmetric case

Introduction

Estimating a low-rank matrix from a noisy observation is a fundamental problem in statistical inference with applications in machine learning, signal processing or information theory. It encompass numerous classical statistical problems from PCA, sparse PCA to high-dimensional Gaussian mixture clustering. Consider a signal matrix $\mathbf{U}\mathbf{V}^{\intercal}$ where $\mathbf{U}$ and $\mathbf{V}$ are two $n\times k$ and $m\times k$ independent matrices. We will be interested in the low-rank, high-dimensional setting, i.e. $k$ will remain fixed as $n,m\to\infty$ and $m/n\to\alpha>0$. Given a noisy observation $\mathbf{Y}$ of the matrix $\mathbf{U}\mathbf{V}^{\intercal}$ we would like to reconstruct the signal. We consider here additive white Gaussian noise $\mathbf{Z}$ (where $Z_{i,j}\overset{\text{\tiny i.i.d.}}{\sim}\mathcal{N}(0,1)$):

where $\lambda$ captures the strength of the signal. This model is often called “spiked” Wishart model (or spiked covariance model) and was introduced in statistics by Johnstone . In this paper, we aim at computing the best achievable performance (in term of mean squared error) for the estimation of the low-rank signal. We prove limiting expressions for the mutual information $I((\mathbf{U},\mathbf{V});\mathbf{Y})$ and the minimum mean squared error (MMSE), as conjectured in . This allows us to compute the information-theoretic threshold for this estimation problem. More precisely, we derive a critical value $\lambda_{c}$ such that when $\lambda<\lambda_{c}$ no algorithm can retrieve the signal better than a “random guess” whereas for $\lambda>\lambda_{c}$ the signal can be estimated more accurately. As mentioned above, high-dimensional Gaussian mixture clustering can be seen as a particular instance of the matrix factorization problem (1) (see ). The present work justify therefore the non-rigorous derivation of the information-theoretic threshold for Gaussian mixture clustering from .

Random matrix models like (1) has received much attention in random matrix theory. In 1976 Edwards and Jones observed using the non-rigorous “replica” method: “there is a critical finite value [for $\lambda$] above which a single eigenvalue [of $\mathbf{Y}/\sqrt{n}$] splits off from the semi-circular continuum of eigenvalues”. This phase transition phenomenon for the largest eigenvalue of perturbed random matrices has then been rigorously understood in the seminal work of Baik, Ben Arous and Péché and following papers . Suppose for instance that $\mathbf{U}$ and $\mathbf{V}$ are vectors with i.i.d. coefficients with zero mean and unit variance. Results from give then

if $\lambda\leq 1$, the top singular value of $\mathbf{Y}/\sqrt{n}$ converges a.s. to $2$ as $n\to\infty$. Let $\mathbf{\hat{u}}$ and $\mathbf{\hat{v}}$ be the respectively the left and right unit singular vectors of $\mathbf{Y}/\sqrt{n}$ associated with this top singular value. Then $\mathbf{\hat{u}}$ and $\mathbf{\hat{v}}$ have trivial correlation with the planted solution: $\frac{1}{n}\mathbf{\hat{u}}^{\intercal}\mathbf{U}\to 0$ and $\frac{1}{n}\mathbf{\hat{v}}^{\intercal}\mathbf{V}\to 0$.

if $\lambda>1$, the top eigenvalue of $\mathbf{Y}/\sqrt{n}$ converges a.s. to $\sqrt{\lambda}+1/\sqrt{\lambda}>2$ as $n\to\infty$. Let $\mathbf{\hat{u}}$ and $\mathbf{\hat{v}}$ be the respectively the left and right unit singular vectors of $\mathbf{Y}/\sqrt{n}$ associated with this top singular value. Then $\mathbf{\hat{u}}$ and $\mathbf{\hat{v}}$ achieve a non-trivial correlation with the solution: $(\frac{1}{n}\mathbf{\hat{u}}^{\intercal}\mathbf{U})^{2}\to 1-1/\lambda$ and $(\frac{1}{n}\mathbf{\hat{v}}^{\intercal}\mathbf{V})^{2}\to 1-1/\lambda$.

This means that when $\lambda$ goes below $1$, the singular vector associated with the top singular value becomes suddenly uninformative. The question then arises: is it still possible to build a non trivial estimator of the signal when $\lambda\leq 1$ ? How does the optimal performance depends on $\lambda$ and the priors $P_{U}$ and $P_{V}$ on the entries of $\mathbf{U}$ and $\mathbf{V}$?

To answer this question, one has to analyze the performance of the optimal estimator (in term of mean squared error). This estimator is known to be the posterior mean of the signal given the observations. However computing such an estimator leads to untractable expressions and exponential-time algorithms. This motivated the study of efficient message passing algorithms for solving the matrix factorization problem (1). Rangan and Fletcher proposed an Approximate Message Passing (AMP) algorithm (based on the previous work of ) to estimate the low-rank signal. Deshpande and Montanari considered then the case of Bernoulli $\text{Ber}(\epsilon)$ priors and showed that AMP was optimal for $\epsilon$ above a certain critical value $\epsilon_{*}>0$. Interestingly, Lesieur et al. conjectured using non-rigorous methods from statistical physics that the estimation problem may become hard for $\epsilon\leq\epsilon_{*}$: it would still be possible to recover the signal partially, but not with AMP or any polynomial-time algorithm. Consequently, a careful analysis of AMP algorithm as in would fail to derive information-theoretic threshold in the presence of such hard phase. Lesieur et al. also conjectured in limiting expression for the mutual information and the MMSE. This conjecture was recently proved for the symmetric ($\mathbf{U}=\mathbf{V}$) case by .

A completely different proof technique based on second moment computations and contiguity has been used to derive upper and lower bounds for the information-theoretic threshold. See the recent works and the references therein. These bounds are however not expected to be tight in the regime considered in this paper.

In this paper we extend and deepen the ideas of to prove the limiting expressions for the mutual information and the MMSE conjectured in . It builds on the mathematical approach of the Sherrington-Kirkpatrick (SK) model: see the books of Talagrand and Panchenko . Our estimation problem is indeed equivalent to a bipartite spin glass model that is closely related to SK model studied in the groundbreaking book of Mézard, Parisi and Virasoro . The methods developed in have then been widely applied to other spin glass models, and in particular models arising from Bayesian estimation problems. This class of models enjoys specific properties due to the presence of the planted (hidden) solution of the estimation problem and to the fact that the parameters of the inference channel (noise, priors…) are supposed to be known by the statistician. In the statistical physics jargon, the system is on the “Nishimori line” (see ), a region of the phase diagram where no “replica symmetry breaking” occurs. These properties will play a crucial role in our proofs. They imply that important quantities will concentrate around their means: the system will then be characterized using only few parameters. For a detailed introduction to the connections between statistical physics and statistical inference, see . Bipartite spin glasses are also of special interest because they are related to Hopfield model . The bipartite SK model has been investigated in , but the study relies on an additional hypothesis, namely the “replica-symmetric” assumption which will be verified for our “planted” model.

Acknowledgments. The author is grateful to M. Lelarge for numerous comments and feedback and to L. Zdeborová and F. Krzakala for pointing out interesting papers.

Main results

We will be interested in the high-dimensional limit where $n,m\to\infty$ while $m/n\to\alpha>0$. Our main quantity of interest is the minimal mean squared error for the estimation of the matrix $\mathbf{U}\mathbf{V}^{\intercal}$ given the observation of the matrix $\mathbf{Y}$:

Our goal is to locate the information-theoretic threshold for the estimation problem (2), i.e. the value of $\lambda$ below which it not possible to estimate the matrix better than a dummy estimator, when $n\to\infty$. We need therefore to compute the limit of ${{\rm MMSE}}_{n}(\lambda)$ as $n\to\infty$, for any value of $\lambda$. We will see in the sequel that this reduces to the computation of the limit of the mutual information \frac{1}{n}I\big{(}(\mathbf{U},\mathbf{V});\mathbf{Y}\big{)}.

2 Connection with statistical physics

We will now connect our statistical estimation problem (2) with statistical physics concepts, namely the notions of Hamiltonian, free energy, replicas and overlap. It will be convenient to express the posterior distribution of $(\mathbf{U},\mathbf{V})$ given $\mathbf{Y}$ in a “Boltzmann” form. We define the Hamiltonian

The posterior distribution of $(\mathbf{U},\mathbf{V})$ given $\mathbf{Y}$ is then

where $\mathcal{Z}_{n}=\!\!\int\!dP_{U}^{\otimes n}(\mathbf{u})dP_{V}^{\otimes m}(\mathbf{v})e^{H_{n}(\mathbf{u},\mathbf{v})}$ is the appropriate normalization. The free energy of this model is defined as

In statistical physics, the free energy is a fundamental quantity that encodes a lot of information about the system. For instance, its derivative with respect to the inverse temperature corresponds to the average energy. In our context of statistical inference, the free energy contains a lot of relevant information about our estimation problem. In particular, we will see that it corresponds (up to an affine transformation) to the mutual information \frac{1}{n}I\big{(}(\mathbf{U},\mathbf{V});\mathbf{Y}\big{)} of the observation channel. Moreover, its derivative with respect to the signal-to-noise ratio $\lambda$ (which plays the role of the inverse temperature) is linked to the minimum mean-square error of our problem by the “I-MMSE Theorem”, see . The asymptotic behavior of the mutual information and the ${{\rm MMSE}}$ will therefore be linked to the limit of the free energy.

We will now illustrate the concepts of Gibbs distribution, replicas and the Nishimori identity by computing the derivative of the free energy $F_{n}$ with respect to the signal $\lambda$. The arguments used in this computation will be used repeatedly in the proofs of this paper. $\lambda\mapsto F_{n}$ is differentiable over $(0,+\infty)$ and for $\lambda>0$

where $(\mathbf{u},\mathbf{v})$ is a replica sampled from the Gibbs distribution $\langle\cdot\rangle_{n}$. Let $1\leq i,j\leq n$. Using the Gaussian integration by parts, we have

3 Effective scalar channel

As we will see in Theorem 1, the limit of $F_{n}$ is linked to a simple 1-dimensional inference problem. Let $P_{X}$ be a probability distribution with finite second moment. Let $\gamma\geq 0$ and consider the following observation channel:

where the signal $X\sim P_{X}$ and the noise $Z\sim\mathcal{N}(0,1)$ are independent random variables. Note that the posterior distribution of $X$ knowing $Y$ is then given by

where $\mathcal{Z}(Y)$ is the normalization: $\mathcal{Z}(Y)=\int dP_{X}(x)e^{Y\sqrt{\gamma}x-\frac{\gamma x^{2}}{2}}=\int dP_{X}(x)e^{\gamma xX+\sqrt{\gamma}xZ-\frac{\gamma x^{2}}{2}}$. We define

The main properties of the functions $\psi_{P_{X}}$ and $F_{P_{X}}$ are presented in Appendix A.1. In the sequel we will consider the scalar channel (7) for $P_{X}=P_{U}$ or $P_{X}=P_{V}$. We will be interested in values of the signal intensity $(\gamma_{1},\gamma_{2})$ that satisfy fixed some point equations.

We define the set $\Gamma(\lambda,\alpha)$ as

A simple application of Brouwer’s fixed point Theorem (see Proposition 13 in Appendix A.2) gives that $\Gamma(\lambda,\alpha)\neq\emptyset$.

4 The Replica-Symmetric formula and its consequences

The limit of $F_{n}$ is expressed using the following function

$\mathcal{F}$ corresponds to the free energy of the two scalar channels (7) associated to $P_{U}$ and $P_{V}$, minus the term $\frac{\lambda\alpha}{2}q_{u}q_{v}$. The Replica-Symmetric formula states that the free energy $F_{n}$ converges to the supremum of $\mathcal{F}$ over $\Gamma(\lambda,\alpha)$.

Moreover, these extrema are achieved over the same couples $(q_{u},q_{v})\in\Gamma(\lambda,\alpha)$.

Theorem 1 is (with Theorem 2 that generalizes the result to any multidimensional input distribution) the main result of this paper and is proved in Section 5. This proves a conjecture from , in particular $\mathcal{F}$ corresponds to the “Bethe free energy” (, Equation 47). The Replica-Symmetric formula allows to compute the limit of the mutual information for the inference channel (2).

Proof . The joint distribution $P_{(\mathbf{U},\mathbf{V};\mathbf{Y})}$ is absolutely continuous with respect to the product $P_{(\mathbf{U},\mathbf{V})}\otimes P_{\mathbf{Y}}$ with Radon-Nikodym derivative:

Therefore the mutual information is equal to

Theorem 1 allows also to compute the limit of the ${{\rm MMSE}}$:

Then $D_{\alpha}$ is equal to $(0,+\infty)$ minus a countable set and for all $\lambda\in D_{\alpha}$ (and thus almost every $\lambda>0$)

Again, this was conjectured in : the performance of the Bayes-optimal estimator (i.e. the MMSE) corresponds to the fixed point of the state-evolution equations (11) which has the greatest Bethe free energy $\mathcal{F}$. Before proving Proposition 2, let us deduce the information-theoretic threshold for our matrix estimation problem. Let us define

If the set of the left-hand side is empty, one define $\lambda_{c}(\alpha)=0$. Proposition 2 gives that $\lambda_{c}(\alpha)$ is the information-theoretic threshold for the estimation of $\mathbf{U}\mathbf{V}^{\intercal}$ given $\mathbf{Y}$:

If $\lambda<\lambda_{c}(\alpha)$, then ${{\rm MMSE}}_{n}(\lambda)\xrightarrow[n\to\infty]{}{{\rm DMSE}}$. It is not possible to reconstruct the signal $\mathbf{U}\mathbf{V}^{\intercal}$ better than a “dummy” estimator.

If $\lambda>\lambda_{c}(\alpha)$, then $\lim\limits_{n\to\infty}{{\rm MMSE}}_{n}(\lambda)<{{\rm DMSE}}$. It is possible to reconstruct the signal $\mathbf{U}\mathbf{V}^{\intercal}$ better than a “dummy” estimator.

Proof of Proposition 2. Let $\lambda>0$. Compute, using the Nishimori identity (Proposition 1),

where we used Equation (6) in the last equality. ${{\rm MMSE}}_{n}$ is a non-increasing function of the signal-to-noise ratio $\lambda$. Consequently, $F_{n}^{\prime}$ is non-decreasing: $\lambda\mapsto F_{n}(\lambda)$ is convex. Define the function

The value of the infimum over $q_{u}$ does not depend on $\lambda$ and $\lambda\mapsto\psi_{P_{U}}(\lambda\alpha q_{v})$ is differentiable with derivative equal to $\frac{\alpha q_{v}}{2}F_{P_{U}}(\lambda\alpha q_{v})$. The supremum over $q_{v}$ is achieved over a compact set (by Theorem 1, because $\Gamma(\lambda,\alpha)$ is compact), thus an envelope theorem (Corollary 4 from ) gives that $\Phi_{\alpha}$ is differentiable at $\lambda>0$ if and only if

is a singleton. By strict monotonicity of $F_{P_{U}}$ (see Lemma 9), one see that $\Phi_{\alpha}$ is differentiable at $\lambda$ if and only if there is only one couple $(q_{u},q_{v})\in\Gamma(\lambda,\alpha)$ that achieves the extrema in (12). Therefore, the set of point at which $\Phi_{\alpha}$ is differentiable is exactly $D_{\alpha}$ and for all $\lambda\in D_{\alpha}$:

$\Phi_{\alpha}$ is convex (as a limit of convex functions) and is thus differentiable everywhere except a countable set. This proves the first assertion. By definition, $F_{n}(\lambda)\to\Phi_{\alpha}(\lambda)$ for all $\lambda>0$. By convexity of $F_{n}$ and $\Phi_{\alpha}$, a standard analysis lemma gives that for all $\lambda\in D_{\alpha}$, $F_{n}^{\prime}(\lambda)\xrightarrow[n\to\infty]{}\Phi_{\alpha}^{\prime}(\lambda)$. The lemma follows. $\square$

5 Numerical experiments

In this section we illustrate our results with numerical experiment: we compute the MMSE for different priors and noise levels. For simplicity, we will considers priors for $U$ and $V$ with zero mean, unit variance and with 2 values in their support:

where $0<p_{u},p_{v}<1$ characterize the asymmetry of the priors. We will first compare the performance of PCA with the MMSE. The results of mentioned in the introduction give:

For the symmetric case ($p_{u}=p_{v}=1/2$), we see that PCA achieves a non-trivial performance as soon it is information-theoretically possible to estimate the signal ($\lambda>1$). It is however sub-optimal. In the asymmetric case, the information-theoretic threshold $\lambda_{c}$ is strictly below $1$. Thus, for $\lambda_{c}<\lambda<1$, it is theoretically possible to achieve a non trivial performance but PCA fails. It is conjectured that any polynomial-time algorithm would fail in this regime (see for instance ).

6 Algorithmic interpretation: Approximate Message Passing (AMP)

Approximate Message Passing (AMP) algorithms, introduced in , have been widely used to study the matrix factorization problem (2). They have been used in for the rank-one case and then in for finite-rank matrix estimation. For detailed review and developments about the study of matrix factorization with message-passing algorithms, see .

We introduce briefly the AMP algorithm and comment its connections with the results of the previous sections. More details about the algorithm and numerical experiments can be found in and . We would not give any proof about AMP, but the results presented here can be deduced from and the previously mentioned articles.

The scalar channel presented in Section 2.3 holds a key role in the AMP algorithm. Suppose that we observed $Y_{u}$ and $Y_{v}$ that are noisy observation of respectively $U$ and $V$ through the scalar channel (7) with signal intensities $\gamma_{u}$ and $\gamma_{v}$. The best predictions that we can make (in term of mean squared error) for $U$ and $V$ are respectively

The AMP algorithm initializes two estimates of $\mathbf{U}$ and $\mathbf{V}$ by setting $(\hat{u}^{0}_{i})_{1\leq i\leq n}\overset{\text{\tiny i.i.d.}}{\sim}P_{U}$, $(\hat{v}^{0}_{j})_{1\leq j\leq m}\overset{\text{\tiny i.i.d.}}{\sim}P_{V}$, and follows the recursion

where we extend the functions $f_{u}$ and $f_{v}$ to vector inputs by applying them coordinate by coordinate. The scalars $\delta_{u}^{t}$ and $\delta_{v}^{t}$ are linked to the partial derivatives of the functions $f_{u}(\cdot,\lambda\alpha q_{v}^{t})$ and $f_{v}(\cdot,\lambda q_{u}^{t})$:

After $t$ iterations, the algorithm outputs $\mathbf{\hat{u}}^{t}(\mathbf{\hat{v}}^{t})^{\intercal}$. The AMP algorithm is particularly interesting because its evolution can be rigorously tracked (see ). For $t\geq 1$, we have almost-surely

The state evolution (19) characterizes therefore the behavior of the AMP algorithm. We see that if $(q_{u}^{t},q_{v}^{t})_{t\geq 0}$ converges to the fixed point $(q_{u}^{*},q_{v}^{*})\in\Gamma(\lambda,\alpha)$ that maximizes $\mathcal{F}(\lambda,\alpha,\cdot,\cdot)$, then the AMP algorithm is an optimal, polynomial-time algorithm. The AMP algorithm is conjectured to be the most efficient polynomial-time algorithm, even in the regime where it does not converges to the optimal fixed point.

7 Extension to rank-k𝑘k matrix estimation

We extend in this section the main results of Section 2.1 multidimensional input distributions.

where $Z_{i,j}$ are i.i.d. standard normal random variables. Similarly to Section 2.1 we define the minimal mean squared error for the estimation of the matrix $\mathbf{U}\mathbf{V}^{\intercal}$ given the observation of the matrix $\mathbf{Y}$:

where the minimum is taken over all estimators $\hat{\theta}$ (i.e. measurable functions of the observations $\mathbf{Y}$). Define the Hamiltonian

We can generalize the definition of the functions $F_{P_{U}}$ and $F_{P_{V}}$ in Section 2.3 to the multidimensional case, and define (see Appendix A.1) for $P_{X}=P_{U},P_{V}$:

where the expectation is taken with respect $(\mathbf{X},\mathbf{Z})\sim P_{X}\otimes\mathcal{N}(\mathbf{0},\mathbf{I}_{k})$ and $S_{k}^{+}$ is the set of $k\times k$ positive semidefinite matrices. We define also

The main properties of the functions $\psi_{P_{X}}$ and $F_{P_{X}}$ are presented in Appendix A.1.

We define the set $\Gamma(\lambda,\alpha)$ as

An application of Brouwer’s fixed point Theorem (see Proposition 13 in Appendix A.2) gives that $\Gamma(\lambda,\alpha)\neq\emptyset$. Similarly to the unidimensional case we will express the limit of $F_{n}$ using the functions $\psi_{P_{U}}$ and $\psi_{P_{V}}$. Let

Moreover, these extrema are achieved over the same couples $(\mathbf{q}_{u},\mathbf{q}_{v})\in\Gamma(\lambda,\alpha)$.

For all $\alpha>0$ we have for almost all $\lambda>0$ that all the optimal couples $(\mathbf{q}_{u},\mathbf{q}_{v})$ of (23) have the same scalar product ${{\rm Tr}}[\mathbf{q}_{u}\mathbf{q}_{v}]=Q(\lambda,\alpha)$ and

The proof of Proposition 3 is a simple extension of the proof of Proposition 2 and is therefore left to the reader.

Proof technique

Our proof technique is closely related to that deals with symmetric matrices. It adapts two techniques that originated from the study of the SK model:

A lower bound on limit of the free energy follows from an application of Guerra’s interpolation technique for the SK model (see or ).

The converse upper bound is proved (as in ) via cavity computations, inspired from the “Aizenman-Sims-Starr scheme” (see or ).

However, our inference model differs from the SK model in a crucial point. Under a small perturbation of the model (2), the overlap between the planted solution $(\mathbf{U},\mathbf{V})$ and a sample $(\mathbf{u},\mathbf{v})$ from the posterior distribution concentrates around its mean (such behavior is called “Replica-Symmetric” in statistical physics). This property is verified for a wide class of inference problems and is a major difference with the SK model, where the overlap concentrates only at high temperature.

For this reason one has to investigate further the overlap distribution to by-pass this lack of convexity. We mentioned above that the overlaps concentrates around their means. We will show in Section 5.2 that these mean values satisfies asymptotically fixed point equations. These equations are related to the TAP equations for the SK model (see , ) and are called “state evolution equations” in the study of Approximate Message Passing (AMP) algorithms (see Section 2.6 and ). Combining these state evolution equations to the classical Guerra’s interpolation scheme allows to derive a tight lower bound.

A decorrelation principle

We present here a general concentration result for the overlap between two replicas (i.e. a sample from a posterior distribution), for a large class of inference problems. This result will hold under some small perturbation of the inference model, which will correspond to some (small) side-information given to the statistician. This is the analog of the Ghirlanda-Guerra identities (see ) for the SK model: the proof will thus be closely related to the derivation of the Ghirlanda-Guerra identities from . In the context of Bayesian inference, a similar result was proved in for the case of CDMA systems with binary inputs.

Suppose that the distribution of $\mathbf{X}$ given $\mathbf{Y}$ takes the following form

From now we will simply write $H_{n}(\mathbf{x})$ instead of $H_{n}(\mathbf{x},\mathbf{Y})$. Let us consider a small “perturbation” of our model: suppose that we have some extra side-information on $\mathbf{X}$ that takes the form:

$\mathcal{Z}_{n,a}^{\text{(pert)}}$ is the appropriate normalization. We will denote by $\langle\cdot\rangle_{n,a}$ the expectation with respect to the posterior distribution of $\mathbf{X}$ given $\mathbf{Y},\mathbf{Y}^{\prime}$. We will write:

for all $k\geq 1$ and all function $f$ for which this integral is well defined. The perturbed free energy is

The next Lemma tells us that if $s_{n}\to 0$, then the perturbation does not affect the limit of the free-energy:

We have for all $a\geq 0$, \big{|}F_{n}-F_{n,a}^{\text{(pert)}}\big{|}\leq 2K^{2}a^{2}s_{n}.

Theorem 3 is the analog of Theorem 3.2 (the Ghirlanda-Guerra identities, see ) from and is proved analogously in Appendix B.1.

Proof of Theorem 1

The proof of Theorem 1 is divided in four steps. In Section 5.1 we apply the Theorem 3 above to our matrix estimation problem to show that the overlaps concentrates around their expectations. In Section 5.2, we show that the overlaps satisfy asymptotically some fixed point equations. In Section 5.3, we prove a lower bound for the limit of $F_{n}$. In Section 5.4, we use similar arguments as in to obtain an upper bound on the limit, which will be revealed to be tight in Section 5.5.

We will only prove the first equality in Theorem 1, since the second follows from the “sup-inf” formula Proposition 14 in Appendix A.3. In order to simplify the proof we are going to prove Theorem 1 in the case where $P_{U}$ and $P_{V}$ have finite (and thus bounded) support $S\subset[-K,K]$. The general case can be deduced from this case by approximating $P_{U}$ and $P_{V}$ by mixtures of Diracs as in , Section 6.2.2. Since the dependency in $\lambda$ can be incorporated in the vector $\mathbf{U}$ (and therefore in the prior $P_{U}$), we can restrict ourselves to the case $\lambda=1$. For simplicity, we are going to consider the case where $n=m$, i.e. $\alpha=1$. The proof for general $\alpha$ can be directly deduced from the proof for $\alpha=1$. Indeed, assume that $\alpha\in(0,1)$ (the case $\alpha>1$ follows simply by symmetry). Let $B_{1},\dots,B_{n}\overset{\text{\tiny i.i.d.}}{\sim}\text{Ber}(\alpha)$, independently of everything else. Since $\frac{1}{n}\sum B_{i}$ concentrates tightly around $\alpha$, is is easy to show that the free energy $F_{n}$ is equal (up to a vanishing term) to the free energy of the observation channel

Therefore, the case $\alpha<1$ will only add some Bernoulli random variables $B_{i}$ in the proof for $\alpha=1$ without changing the arguments.

For reasons mentioned above, we will suppose in this section to be in the case $\alpha=1$ and $\lambda=1$, and remove all dependencies in this variables: we will simply write $\Gamma$ instead of $\Gamma(\lambda,\alpha)$ and $\mathcal{F}(q_{u},q_{v})$ instead of $\mathcal{F}(\lambda,\alpha,q_{u},q_{v})$. We will use the notation $P_{0}=P_{U}\otimes P_{V}$.

In this section we apply the results of the previous section to our model (2). We will need to consider an inference model that is slightly more general than (2). Let $(U_{i},V_{i})_{1\leq i\leq n}\overset{\text{\tiny i.i.d.}}{\sim}P_{0}$ and suppose that we observe

Similarly, one can associate to the observations (27) the Hamiltonian:

The observations (28) correspond to a small amount of side-information that will allow us to prove some concentration result for the overlaps as in Section 4. The corresponding Hamiltonians read

We write, for $\mathbf{u},\mathbf{v}\in S^{n}$, $H_{n}^{\text{(pert)}}(\mathbf{u},\mathbf{v})=H_{n,u}^{\text{(pert)}}(\mathbf{u})+H_{n,v}^{\text{(pert)}}(\mathbf{v})$ and define the “total” Hamiltonian as $H_{n}^{\text{(tot)}}=H_{n}+H_{n}^{(s)}+H_{n}^{\text{(pert)}}$. The posterior distribution of $(\mathbf{U},\mathbf{V})$ given $\mathsf{Y}=(\mathbf{Y},\mathbf{Y}^{(u)},\mathbf{Y}^{(v)},\mathbf{Y}^{(u)\prime},\mathbf{Y}^{(v)\prime})$ reads

where $\mathcal{Z}_{n}^{\text{(tot)}}$ is the appropriate normalization. Let $\langle\cdot\rangle_{n,a}$ be the associated Gibbs measure on $(S^{n})^{2}$:

An application of the decorrelation principle of Section 4 (see Appendix B.2 for a proof) gives

2 Fixed point equations

We have seen (in Proposition 4) that the overlaps $\mathbf{u}^{(1)}.\mathbf{u}^{(2)}$ and $\mathbf{v}^{(1)}.\mathbf{v}^{(2)}$ concentrates asymptotically around their expectations. In this section, we show that these expected values satisfy fixed point equations, in the $n\to\infty$ limit. The analysis is an adaptation of the derivation of the TAP equations for the SK model, see .

To obtain these fixed point equations, we are going to do what physicists call “cavity computations”: we compare the system with $2n$ variables to the system with $2n+2$ variables to study the influence of the “first” $2n$ variables on the $2$ “last” variables we add.

Similarly, one can decompose the Hamiltonians $H_{n}^{(s)}$ and $H_{n+1}^{\text{(pert)}}$

Let us now define $H_{n}^{\text{(tot)}\prime}=H_{n}^{\prime}+H_{n}^{(s)}+H_{n}^{\text{(pert)}\prime}$ and $\langle\cdot\rangle^{\prime}_{n,a}$ the Gibbs measure on $(S^{n})^{2}$ corresponding to the Hamiltonian $H_{n}^{\text{(tot)}\prime}$. An easy adaptation of Proposition 4 gives that the overlaps under the Gibbs measure $\langle\cdot\rangle^{\prime}_{n,a}$ concentrate around their expectations:

(recall the short notation $U^{\prime}=U_{n+1}$ and $V^{\prime}=V_{n+1}$) where

Let $\langle\cdot\rangle_{n+1,a}$ be the Gibbs measure on $(S^{n+1})^{2}$ associated with the Hamiltonian $H_{n+1}^{\text{(tot)}}=H_{n+1}+H_{n+1}^{(s)}+H_{n+1}^{\text{(pert)}}$ as defined by (32).

Proof . By the definition of $y$ (see Equation (38)) we have

Proof . By the definition of $y$ (see equation (38)) we have

by Cauchy-Schwarz’s inequality. The bounded support assumption on $P_{0}$ implies that, there exists a constant $C_{2}$ such that, for all $u_{1}^{\prime},v_{1}^{\prime},u_{2}^{\prime},v_{2}^{\prime}\in S$ and $\mathbf{u}^{(1)},\mathbf{v}^{(1)},\mathbf{u}^{(2)},\mathbf{v}^{(2)}\in S^{n}$ we have

And the right hand side goes to as $n\to\infty$ by (37). This concludes the proof. $\square$

The variables $u_{i}$ are bounded, so \big{|}\frac{1}{n+1}\sum_{i=1}^{n+1}\langle u_{i}\rangle_{n+1,a}^{2}-\frac{1}{n}\sum_{i=1}^{n}\langle u_{i}\rangle_{n+1,a}^{2}\big{|}=O(n^{-1}), hence the result. $\square$

Let $Z_{1},Z_{2}\overset{\text{\tiny i.i.d.}}{\sim}\mathcal{N}(0,1)$ and define for $\gamma_{1},\gamma_{2}\geq 0$

Proof . Define for $u^{\prime},v^{\prime}\in S$

Notice that $(U^{\prime},V^{\prime},(h_{0}(u^{\prime},v^{\prime}))_{u^{\prime},v^{\prime}\in S})=(U^{\prime},V^{\prime},(h_{1}(u^{\prime},v^{\prime}))_{u^{\prime},v^{\prime}\in S})$ in law. Indeed, conditionally to $(U^{\prime},V^{\prime})$ and $(\langle u_{i}\rangle^{\prime}_{n,a},\langle v_{i}\rangle^{\prime}_{n,a})_{1\leq i\leq n}$, $(h_{0}(u^{\prime},v^{\prime}))_{u^{\prime},v^{\prime}\in S}$ and $(h_{1}(u^{\prime},v^{\prime}))_{u^{\prime},v^{\prime}\in S}$ are two Gaussian processes with the same covariance structure. Consequently,

The function $F_{\phi}$ is $\mathcal{C}^{1}$ and therefore Lipschitz on the compact set $C=[q_{u}-K^{2},q_{u}+K^{2}]\times[q_{v}-K^{2},q_{v}+K^{2}]$. We note $L_{0}$ its Lipschitz constant. $(\frac{n}{n+1}tQ_{v}^{\prime}+q_{u},\frac{n}{n+1}tQ_{u}^{\prime}+q_{v})$ belongs to $C$ with probability $1$, therefore

The expectation of the right hand side with respect to $a_{u}$ and $a_{v}$ goes to zero as $n\to\infty$ because the overlaps under $\langle\cdot\rangle^{\prime}_{n,a}$ concentrate around their expectations (see Equation 37), and because of Corollary 2. This concludes the proof. $\square$

We remark that the function $F_{P_{U}}$ defined as in (9) corresponds to $F_{\phi}$ obtained for the choice $\phi(u_{1},v_{1},u_{2},v_{2})=u_{1}u_{2}$. Similarly, $F_{P_{V}}$ (defined as in (9)) is the function $F_{\phi}$ obtained for $\phi(u_{1},v_{1},u_{2},v_{2})=v_{1}v_{2}$. Proposition 5 implies then that the overlaps satisfy asymptotically two fixed point equations.

3 The lower bound: interpolation method

The lower bound is proved using Guerra’s interpolation technique , originally developed for the SK model. In the context of bipartite spin glasses, this interpolation scheme has been used in under a “replica symmetric” assumption.

Proof . Let $(q_{1},q_{2})\in\Gamma$. Define, for $t\in$, the Hamiltonians

for $\mathbf{u},\mathbf{v}\in S^{n}$, and $H_{n,t}^{\text{(tot)}}=H_{n,t}+H_{n,t}^{(s)}+H_{n}^{\text{(pert)}}$, where $H_{n}^{\text{(pert)}}$ is defined in Section 5.1. Let $\langle\cdot\rangle_{t}$ denotes the Gibbs measure corresponding to the Hamiltonian $H_{n,t}^{\text{(tot)}}$. Define

Let $t\in(0,1)$ be fixed. Using Gaussian integration by parts and the Nishimori identity as we did to prove (6) we compute

because $F_{P_{U}}$ is non-decreasing (Lemma 9). Consequently, by Equation (45), $\liminf_{n\to\infty}\phi^{\prime}(t)\geq-\frac{1}{2}q_{2}q_{1}$. Using Fatou’s lemma

and we conclude using equation (46). $\square$

4 Aizenman - Sims - Starr scheme

We prove in this section an upper bound on the limit of the free energy. We consider the observation system (26-27-28) in the special case $q_{u}=q_{v}=0$ (so $H_{n}^{(s)}=0$) and $t=1$.

Then $H_{n}^{\text{(tot)}}(\mathbf{u},\mathbf{v})=w(\mathbf{u},\mathbf{v})+w^{\text{(pert)}}(\mathbf{u},\mathbf{v})+H_{n}^{\text{(tot)}\prime}(\mathbf{u},\mathbf{v})$ in law. Define the perturbed free energy

It remains therefore to compute the limit of $A_{n}^{\text{(pert)}}$.

because the contribution of $w^{\text{(pert)}}$ is negligible, for the same reasons than in the proof of Lemma 1. Indeed, since $s_{n}=n^{-1/4}$, $s_{n+1}-s_{n}=o(n^{-1})$. Proposition 7 follows then from the following lemma.

Proof . One have $|\log B_{1}-\log B_{2}|\leq\max(B_{1}^{-1},B_{2}^{-1})|B_{1}-B_{2}|$. So that

Let $Z_{1},Z_{2}$ be independent standard Gaussian random variables, independent of everything else. Then the processes $(h_{0}(u^{\prime},v^{\prime}))_{u^{\prime},v^{\prime}\in S}$ and

have the same law. Indeed, conditionally on $(U^{\prime},V^{\prime})$ and $(\langle u_{i}\rangle^{\prime}_{n,a},\langle v_{i}\rangle^{\prime}_{n,a})_{1\leq i\leq n}$ both are Gaussian processes with the same covariance structure. Consequently

5 The final part

We conclude the proof of Theorem 1 in this section, using the results of the previous sections. We still consider the observation system (26-27-28) with $q_{u}=q_{v}=0$ (so $H_{n}^{(s)}=0$) and $t=1$.

Equations (48) and (49) give that $(Q_{u}^{\infty},Q_{v}^{\infty})\in\Gamma$ with probability $1$. Therefore, we have

almost surely. We conclude, using equation (50) that $\limsup F_{n}\leq\sup_{\Gamma}\mathcal{F}$, which proves (combined with Proposition 6) the first expression for the limit of $F_{n}$. Theorem 1 follows then from Proposition 14 in Appendix A.3.

Proof of Theorem 2

The major difference with the proof presented in Section 5 is the kind of perturbation we will add to our observation system, in order to obtain concentration results for the overlaps. Instead of adding low-signal Gaussian scalar channels (see (25)), we will rather reveal each variable $(\mathbf{U}_{i},\mathbf{V}_{i})$ with small probability. Lemma 3.1 from shows that this kind of perturbation forces the correlations to decay. This approach has already been used in and to obtain overlaps concentration.

Let $\epsilon\in$, and suppose we have access to the additional information, for $1\leq i\leq n$

where $L_{i}\overset{\text{\tiny i.i.d.}}{\sim}\text{Ber}(\epsilon)$ and $*$ is a value that does not belong to $S$. The posterior distribution of $(\mathbf{U},\mathbf{V})$ given $(\mathbf{Y},\mathbf{Y^{\prime}})$ is now

where $\mathcal{Z}_{n,\epsilon}$ is the appropriate normalization constant. For $(\mathbf{u},\mathbf{v})\in S^{n}\times S^{n}$ we will use the following notations

$\mathbf{\bar{u}}$ and $\mathbf{\bar{v}}$ are thus obtained by replacing the coordinates of $\mathbf{u}$ and $\mathbf{v}$ that are revealed by $\mathbf{Y}^{\prime}$ by their revealed values. The notations $\mathbf{\bar{u}}$ and $\mathbf{\bar{v}}$ will allow us to obtain a very convenient expression for the free energy of the perturbed model which is defined as

The following Proposition comes from (Proposition 22):

For all $n\geq 1$ and all $\epsilon\in$, we have

It remains therefore to compute the limit of the free energy averaged over small perturbations.

2 Overlap concentration

Let $\langle\cdot\rangle_{n,\epsilon}$ denote the expectation with respect to the posterior distribution (52) of $(\mathbf{U},\mathbf{V})$ given $(\mathbf{Y},\mathbf{Y}^{\prime})$. The Nishimori identity (Proposition 1) will thus be valid under $\langle\cdot\rangle_{n,\epsilon}$. We recall that $\mathbf{Y}^{\prime}$ is defined in (51), where $L_{i}\overset{\text{\tiny i.i.d.}}{\sim}\text{Ber}(\epsilon_{n})$ are independent random variables.

The following lemma comes from (Lemma 3.1). It shows that the extra information $\mathbf{Y}^{\prime}$ forces the correlations to decay.

This implies that the overlap between two replicas, i.e. two independent samples $(\mathbf{u}^{(1)},\mathbf{v}^{(1)})$ and $(\mathbf{u}^{(2)},\mathbf{v}^{(2)})$ from the Gibbs distribution $\langle\cdot\rangle_{n,\epsilon}$, concentrates. Let us define

$\mathbf{Q}_{u}$ and $\mathbf{Q}_{v}$ are two random variables depending only on $(Y_{i,j})_{1\leq i,j\leq n}$ and $(\mathbf{Y}_{i}^{\prime})_{1\leq i\leq n}$. Notice that $\mathbf{Q}_{u},\mathbf{Q}_{v}\in S_{k}^{+}$.

3 Aizenman-Sims-Starr scheme

Using the concentration results of Proposition 9 the proofs of Section 5.4 can be extended to the multidimensional case.

4 Fixed point equations

Let $\mathbf{q}_{u},\mathbf{q}_{v}\in S_{k}^{+}$. Suppose that we have access to the additional observations

where $(\mathbf{Z}_{i}^{(u)})_{1\leq i\leq n}$ and $(\mathbf{Z}_{i}^{(v)})_{1\leq i\leq n}$ are i.i.d. $\mathcal{N}(0,\mathbf{I}_{k})$, independently of everything else. Let $\mathbf{Q_{u}}$ and $\mathbf{Q}_{v}$ be defined as in equations (55) and (56), where the Gibbs measure $\langle\cdot\rangle_{n,\epsilon}$ denotes the posterior distribution of $(U,V)$ given $Y$, $Y^{\prime}$, $Y^{(u)}$ and $Y^{(v)}$. Notice that Proposition 9 still hold for this Gibbs distribution (the proofs are the same). The arguments of Section 5.2 can be extended to the multidimensional case to obtain the multidimensional version of Corollary 3:

5 The lower bound: interpolation method

Proof . Let $(\mathbf{q}_{1},\mathbf{q}_{2})\in\Gamma$. Define, for $t\in$, the Hamiltonians

for $\mathbf{u},\mathbf{v}\in S^{n}$, and $H_{n,t}^{\text{(tot)}}=H_{n,t}+H_{n,t}^{(s)}$. Let $\langle\cdot\rangle_{t}$ be the Gibbs measure defined as

where we recall that the notations $\mathbf{\bar{u}}$ and $\mathbf{\bar{v}}$ are defined by (53-54). Define

Let $t\in(0,1)$ be fixed. Gaussian integration by parts and Nishimori identity lead to

where $o_{n}(1)$ denotes a quantity that goes to as $n\to\infty$, because of the concentration of the overlaps (Proposition 9). By Proposition 11

We have also $\mathbf{q}_{1}=F_{P_{U}}(\mathbf{q}_{2})$. Thus

because $\frac{1}{2}F_{P_{U}}$ is the gradient of the convex function $\psi_{P_{U}}$ (Lemma 9). Consequently, by Equation (58), $\liminf_{n\to\infty}\phi^{\prime}(t)\geq-\frac{1}{2}\mathbf{q}_{2}\mathbf{q}_{1}$. Using Fatou’s lemma

We conclude using equation (59): $\liminf\limits_{n\to\infty}F_{n}\geq\mathcal{F}(\mathbf{q}_{1},\mathbf{q}_{2})$. $\square$

6 The final part

The remaining of the proof is exactly the same than in the unidimensional case (Section 5.5): the variables $\mathbf{Q}_{u}$ and $\mathbf{Q}_{v}$ converge along a subsequence to a point of $\Gamma$, because of Proposition 11. This proves the converse bound of Proposition 12 and thus Theorem 2 (again we use Proposition 14 to obtain the “max-min formula”).

Appendix A The linear Gaussian channel

In this section we will work with positive semi-definite matrices. We will denote by $S_{k}^{+}$ the set of $k\times k$ positive semi-definite matrices. Recall that $S_{k}^{+}$ is a convex cone. We will also use Loewner (partial) order $\preceq$ on $S_{k}^{+}$. For $\mathbf{A},\mathbf{B}\in S_{k}^{+}$,

for any continuous bounded function $f$. Let $\mathbf{x}$ be distributed according to $\langle\cdot\rangle_{\mathbf{q}}$ independently of everything else. We define the overlap function:

It is not difficult to verify that both functions are continuous over $S_{k}^{+}$.

The next lemma states the main properties of the functions $\psi_{P_{X}}$ and $F_{P_{X}}$.

If ${{\rm Cov}}(\mathbf{X})$ is inversible, then $\psi_{P_{X}}$ is strictly convex.

$\psi_{P_{X}}$ is differentiable on $S_{k}^{+}$ and for $\mathbf{q}\in S_{k}^{+}$

$F_{P_{X}}$ is non-decreasing in the sense that, if $\mathbf{q}_{1}\preceq\mathbf{q}_{2}$, then $F_{P_{X}}(\mathbf{q}_{1})\preceq F_{P_{X}}(\mathbf{q}_{2})$. If ${{\rm Cov}}(\mathbf{X})\succ\mathbf{0}$ and $\mathbf{q}_{1}\prec\mathbf{q}_{2}$, then $F_{P_{X}}(\mathbf{q}_{1})\prec F_{P_{X}}(\mathbf{q}_{2})$.

Proof . To prove (i) it suffices to show that $g:t\in\mapsto\psi_{P_{X}}(t\mathbf{q}_{1}+(1-t)\mathbf{q}_{2})$ is convex, for all $\mathbf{q}_{1},\mathbf{q}_{2}\in S_{k}^{+}$.

Let $\mathbf{q}_{1},\mathbf{q}_{2}\in S_{k}^{+}$. Let $\mathbf{Z}_{1},\mathbf{Z}_{2}\sim\mathcal{N}(0,\mathbf{I}_{k})$ two independent standard random variables, independent of any other random variable. Define $\mathbf{q}_{t}=t\mathbf{q}_{1}+(1-t)\mathbf{q}_{2}$. We have

$g$ is continuous on $$, differentiable on$(0,1)$. Let$t\in(0,1)$. Define$\mathbf{q}=\mathbf{q}_{1}-\mathbf{q}_{2}$. We have

where we used successively Gaussian integration by parts and the Nishimori identity. This derivative is continuous in and $1$, so $g$ is also differentiable at those points. This proves (iii). Similar computations shows that for $t\in(0,1)$,

by Lemma 11 below. This proves (i). To prove (ii) is suffices to show that $g^{\prime\prime}(t)>0$ when ${{\rm Cov}}(\mathbf{X})\succ\mathbf{0}$ and $\mathbf{q}_{1}\neq\mathbf{q_{2}}$. Suppose that $g^{\prime\prime}(t)=0$. Then {{\rm Tr}}\Big{[}\big{(}\mathbf{q}(\langle\mathbf{x}\mathbf{x}^{\intercal}\rangle_{\mathbf{q}_{t}}-\langle\mathbf{x}\rangle_{\mathbf{q}_{t}}\langle\mathbf{x}^{\intercal}\rangle_{\mathbf{q}_{t}})\big{)}^{2}\Big{]}=0 almost surely.

If ${{\rm Cov}}(\mathbf{X})\succ\mathbf{0}$ then for all $\mathbf{q}\in S_{k}^{+}$

Combining Lemma 10 and Lemma 11 below, we obtain $\mathbf{q}=0$ which is absurd. This proves (ii).

Now, if $\mathbf{q}^{\prime}\succ\mathbf{0}$, using Lemma 10 we see that $h^{\prime}(t)>0$. This proves (iv). (vi) is obvious. Notice that for $\mathbf{q}\in S_{k}^{+}$

This proves the first part of (v). The second part follows from (iv) and (vii), that we prove now. Let $\mathbf{q}\succ\mathbf{0}$ and apply Lemma 8 with $f(\mathbf{Y})=\mathbf{q}^{-1/2}\mathbf{Y}$:

Let $\mathbf{A}$ and $\mathbf{B}$ be two symmetric matrices. Suppose that $\mathbf{B}$ is semidefinite positive. Then

Moreover, if $\mathbf{B}\succ\mathbf{0}$ we have equality if and only if $\mathbf{A}=\mathbf{0}$.

Proof . $\mathbf{B}$ is semidefinite positive, so it admits a square root $\mathbf{B}^{1/2}$. Define $\mathbf{C}=\mathbf{B}^{1/2}\mathbf{A}\mathbf{B}^{1/2}$. Then

A.2 Fixed points equations

Proof . $F_{P_{U}}$ and $F_{P_{V}}$ take their values (by Lemma 9 (v)) in

which is convex and compact. The function $f:(\mathbf{q}_{u},\mathbf{q}_{v})\mapsto(F_{P_{U}}(\lambda\alpha\mathbf{q}_{v}),F_{P_{V}}(\lambda\mathbf{q}_{u}))$ is continuous from $C$ to $C$. Brouwer’s Theorem gives the existence of a fixed point of $f$: $\Gamma(\lambda,\alpha)\neq\emptyset$. $\square$

A.3 The min-max formula

Recall that $\Gamma(\lambda,\alpha)$ is defined by Definition 1 (for $k=1$) and Definition 2 (for $k\geq 1$).

Suppose that ${{\rm Cov}}(\mathbf{V})\succ\mathbf{0}$. Then

Moreover, these extrema are achieved over the same couples $(\mathbf{q}_{u},\mathbf{q}_{v})\in\Gamma(\lambda,\alpha)$.

Proof . $\Gamma(\lambda,\alpha)$ is a compact set. Let $(\mathbf{q}_{u}^{*},\mathbf{q}_{v}^{*})\in\Gamma(\lambda,\alpha)$ that achieves the supremum of the left-hand side of (62). The function $\mathbf{q}_{u}\in S_{k}^{+}\mapsto\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v}^{*})$ is convex (by Lemma 9) and his gradient at $\mathbf{q}_{u}^{*}$ is equal to

because $(\mathbf{q}_{u}^{*},\mathbf{q}_{v}^{*})\in\Gamma(\lambda,\alpha)$. Thus $\displaystyle\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u}^{*},\mathbf{q}_{v}^{*})=\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v}^{*})\leq\sup_{\mathbf{q}_{v}\in S_{k}^{+}}\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$.

Therefore, $\phi(t)\xrightarrow[t\to+\infty]{}-\infty$ and $\displaystyle\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})=-\infty$. We can thus restrict the supremum to $K_{V}$.

For $\mathbf{q}_{v}\in S_{k}^{+}$ we define $\phi_{\mathbf{q}_{v}}:\mathbf{q}_{u}\in S_{k}^{+}\mapsto\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$ and $f(\mathbf{q}_{v})=\inf_{\mathbf{q}_{u}}\phi_{\mathbf{q}_{v}}(\mathbf{q}_{u})$. Let $\stackrel{{\scriptstyle\circ}}{{K_{V}}}$ denote the interior of $K_{V}$ in $S_{k}^{+}$, that is

If $\mathbf{q}_{v}\in\stackrel{{\scriptstyle\circ}}{{K_{V}}}$, then $\displaystyle\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$ is achieved at a unique $\mathbf{q}_{u}^{*}(\mathbf{q}_{v})\in S_{k}^{+}$. Moreover,

The function $\displaystyle f:\mathbf{q}_{v}\in\stackrel{{\scriptstyle\circ}}{{K_{V}}}\mapsto\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$ is differentiable, with gradient given by

Proof . Let $\mathbf{q}_{v}\in\stackrel{{\scriptstyle\circ}}{{K_{V}}}$ and define $\phi_{\mathbf{q}_{v}}:\mathbf{q}_{u}\mapsto\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$. ${{\rm Cov}}(\mathbf{V})\succ\mathbf{0}$ thus by Lemma 9, $\phi_{\mathbf{q}_{v}}$ is strictly convex with gradient

Consequently, $\phi_{\mathbf{q}_{v}}(\mathbf{q}_{u})\xrightarrow[\mathbf{q}_{u}\to\infty]{}+\infty$. $\phi_{\mathbf{q}_{v}}$ admits therefore a unique minimizer $\mathbf{q}_{u}^{*}(\mathbf{q}_{v})$. (63) follows from the optimality conditions at $\mathbf{q}_{u}^{*}(\mathbf{q}_{v})$.

Let $\mathbf{Q}_{v}\in\stackrel{{\scriptstyle\circ}}{{K_{V}}}$. We are going to show that $f$ is differentiable on $\{\mathbf{q}_{v}\in S_{k}^{+}\ |\ \mathbf{q}_{v}\prec\mathbf{Q}_{v}\}$. $\mathbf{Q}_{v}\prec\Sigma_{V}$ so by Lemma 9 we can find $\mathbf{Q}_{u}\in S_{k}^{+}$ such that for all $\mathbf{q}_{u}\succeq\mathbf{Q}_{u}$, $F_{P_{V}}(\lambda\mathbf{q}_{u})\succ\mathbf{Q}_{v}$. Let now $\mathbf{0}\preceq\mathbf{q}_{v}\prec\mathbf{Q}_{v}$. For all $\mathbf{q}_{u}\succeq\mathbf{Q}_{u}$

Consequently, $\mathbf{q}_{u}^{*}\preceq\mathbf{Q}_{u}$. For $\mathbf{q}_{v}\in\{\mathbf{q}_{v}\in S_{k}^{+}\ |\ \mathbf{q}_{v}\prec\mathbf{Q}_{v}\}$, we have shown that the infimum is achieved at a unique point of a compact set. Thus, by an “envelope theorem” (Corollary 4 from ), $f$ is differentiable on $\{\mathbf{q}_{v}\in S_{k}^{+}\ |\ \mathbf{q}_{v}\prec\mathbf{Q}_{v}\}$ with gradient given by (64). The lemma follows. $\square$

From what we have seen until now, $\stackrel{{\scriptstyle\circ}}{{K_{V}}}\subset D_{V}\subset K_{V}$. Notice that $f:\mathbf{q}_{v}\mapsto\inf_{\mathbf{q}_{u}\in S_{k}^{+}}\mathcal{F}(\lambda,\alpha,\mathbf{q}_{u},\mathbf{q}_{v})$ is continuous over $D_{V}$. Indeed for $\mathbf{q}_{v}\in D_{V}$

and the second term of the right-hand side is a concave function of $\mathbf{q}_{v}$ (as an infimum of linear functions) and is thus continuous. Moreover, one verify easily that if $f(\mathbf{q}_{v})=-\infty$ for some $\mathbf{q}_{v}\in K_{V}$, then $f(\mathbf{q}_{v}^{\prime})\xrightarrow[\mathbf{q}_{v}^{\prime}\in D_{V}\to\mathbf{q}_{v}]{}-\infty$. Consequently the supremum of $f$ is achieved at some $\mathbf{q}_{v}^{*}\in D_{V}$.

Case 1: $\mathbf{q}_{v}^{*}\in\stackrel{{\scriptstyle\circ}}{{K_{V}}}$. By Lemma 12 above, the minimum of $\phi_{\mathbf{q}_{v}^{*}}$ is thus achieved at a unique $\mathbf{q}_{u}^{*}\in S_{k}^{+}$. The optimality condition of $f$ at $\mathbf{q}_{v}^{*}$ gives:

By Lemma 12, $\mathbf{q}_{u}^{*}$ is the unique minimizer of $\phi_{\mathbf{q}_{v}^{*}}$, therefore $\mathbf{q}_{u}^{*}=F_{P_{U}}(\lambda\alpha\mathbf{q}_{v}^{*})$. By (63) we have $F_{P_{V}}(\lambda\mathbf{q}_{u}^{*})\succeq\mathbf{q}_{v}^{*}$. Suppose that $\mathbf{q}_{v}^{*}\neq F_{P_{V}}(\lambda\mathbf{q}_{u}^{*})$. Then by monotonicity of $\psi_{P_{U}}$ (Lemma 9) we have $\psi_{P_{U}}(\lambda\alpha\mathbf{q}_{v}^{*})<\psi_{P_{U}}(\lambda\alpha F_{P_{V}}(\lambda\mathbf{q}_{u}^{*}))$. Thus

which is absurd because $\mathbf{q}_{v}^{*}$ maximizes $f$. We conclude that $\mathbf{q}_{v}^{*}=F_{P_{V}}(\lambda\mathbf{q}_{u}^{*})$ and $(\mathbf{q}_{u}^{*},\mathbf{q}_{v}^{*})\in\Gamma(\lambda,\alpha)$ and therefore

which is absurd. Therefore, there exists $r\in\{1,\dots,k\}$ such that $\mu_{1}=\dots=\mu_{r}=+\infty$ and $\mu_{r+1},\dots,\mu_{k}<\infty$.

for all measurable function $h$, where the last expectation is with respect $\mathbf{V}$ and $\mathbf{Y}=(\mathbf{q}_{u}^{(n)})^{1/2}\mathbf{V}+\mathbf{Z}$, where $(\mathbf{V},\mathbf{Z})\sim P_{V}\otimes\mathcal{N}(\mathbf{0},\mathbf{I}_{k})$. Let $i\in\{1,\dots,r\}$ and let us chose $h(\mathbf{Y})=\frac{1}{\sqrt{\mu_{i}^{(n)}}}\mathbf{Y}$. Compute