Let A∈R^n× n be positive definite, let m≤ n be an iteration index, and let gamma_i, r_i, and widetildev_i denote the quantities defining the covariance approximations in the paper. For a positive integer d(m)≪ n, define Sigma_m=∑_i=m+1^m+d(m)(gamma_i|r_i-1|_2^2)widetildev_i(widetildev_i)^T and widetildeSigma_m=∑_i=m+1^n(gamma_i|r_i-1|_2^2)widetildev_i(widetildev_i)^T. Optimal low-rank covariance approximation conjecture. For almost any positive definite matrix A, for every iteration m≤ n, there exist d(m)≪ n and r(d)≤ d(m) such that Sigma_m is an optimal r(d)-rank approximation to widetildeSigma_m with respect to the operator norm |·|_A,A^-1. The conjecture proposes that a short initial segment of the covariance expansion attains the best approximation of the full covariance at an appropriately chosen rank. This is motivated by the observed decay of |r_i| in exact arithmetic, but the preceding discussion notes that the relevant coefficient sequence need not be monotone, so the claim is not established in general.

Optimal low-rank covariance approximation conjecture for probabilistic projection methods

About 2 years old · traced to 2024

Let $A\in\mathbb{R}^{n\times n}$ be positive definite, let $m\leq n$ be an iteration index, and let $\gamma_i$ , $r_i$ , and $\widetilde{v}_i$ denote the quantities defining the covariance approximations in the paper. For a positive integer $d(m)\ll n$ , define

\Sigma_m=\sum_{i=m+1}^{m+d(m)}\left(\gamma_i\left\|r_{i-1}\right\|_2^2\right)\widetilde{v}_i\left(\widetilde{v}_i\right)^T

and

\widetilde{\Sigma}_m=\sum_{i=m+1}^{n}\left(\gamma_i\left\|r_{i-1}\right\|_2^2\right)\widetilde{v}_i\left(\widetilde{v}_i\right)^T.

Optimal low-rank covariance approximation conjecture. For almost any positive definite matrix $A$ , for every iteration $m\leq n$ , there exist $d(m)\ll n$ and $r(d)\leq d(m)$ such that $\Sigma_m$ is an optimal $r(d)$ -rank approximation to $\widetilde{\Sigma}_m$ with respect to the operator norm $\left\|\cdot\right\|_{A,A^{-1}}$ . The conjecture proposes that a short initial segment of the covariance expansion attains the best approximation of the full covariance at an appropriately chosen rank. This is motivated by the observed decay of $\left\|r_i\right\|$ in exact arithmetic, but the preceding discussion notes that the relevant coefficient sequence need not be monotone, so the claim is not established in general.

References

Primary source

Vladimir Fanaskov, “Uncertainty calibration for probabilistic projection methods”, arXiv:2402.05562 (2024).

covariance-estimation low-rank-approximation numerical-linear-algebra

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

The conjecture remains unproved, but a reader-written construction claims to disprove it on open sets of matrices in every dimension at least three.

Fanaskov posed the statement as Conjecture 1 in 2024: a short chronological prefix of the covariance expansion should be an optimal low-rank approximation to the full remainder for almost every positive definite $A$ .

Known results

Fanaskov (2024) proved optimality for non-increasing coefficients $\gamma_i\lVert r_{i-1}\rVert_2^2$ .
Fanaskov (2024) noted that these coefficients need not be monotone, despite residual convergence in exact arithmetic, and presented numerical cases with both favorable and unfavorable truncations.

Reader-written counterexample claim

A construction with $n\ge3$ , $a>1$ , and a tridiagonal positive definite matrix claims that the covariance weights increase strictly, so every proper chronological prefix has error $a^{2n-2}$ while a rank-one approximation using the final direction has smaller error. It further claims the failure persists on open sets and realizes arbitrary positive weight profiles. This is a complete counterexample claim, but it has not been independently verified.

Current status (as of August 2026): Fanaskov's conjecture remains unproved in the published record, while an unverified reader-written counterexample claim would invalidate it if correct.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

Counterexample on open sets in every dimension. The conjecture is Conjecture 1 of Fanaskov, Statistics and Computing 31 (2021), article 56, also reproduced in Section 8.1 of arXiv:2402.05562. Classical flexibility of conjugate-gradient convergence curves was previously established by Meurant, Numerical Algorithms 84 (2020). The construction below identifies the exact covariance weights in Fanaskov's conjecture and disproves its asserted almost-everywhere optimality.

Let $n\ge3$ , $a>1$ , and define

L=I_n+a\sum_{j=1}^{n-1}e_{j+1}e_j^{\mathsf T}, \qquad A=LL^{\mathsf T},\qquad b=e_1,\qquad x_0=0.

Thus $A$ is strictly positive definite; explicitly,

A=\begin{pmatrix} 1&a&0&\cdots&0\\ a&1+a^2&a&\ddots&\vdots\\ 0&a&1+a^2&\ddots&0\\ \vdots&\ddots&\ddots&\ddots&a\\ 0&\cdots&0&a&1+a^2 \end{pmatrix}.

Since $A$ is irreducibly tridiagonal, $\mathcal K_j(A,e_1)=\operatorname{span}(e_1,\ldots,e_j)$ . The conjugate-gradient iterate is its Galerkin solution. The leading-block Cholesky factor gives

(x_j)_j=(-a)^{j-1}, \qquad r_j=(-a)^je_{j+1}\quad(0\le j<n).

Hence, with exactly the source's Algorithm 2 notation,

\gamma_j=1,\qquad \eta_j=a^{2j-2},\qquad c_j:=\gamma_j\|r_{j-1}\|_2^2=a^{2j-2}.

Therefore all covariance weights are strictly increasing:

1=c_1<c_2<\cdots<c_n=a^{2n-2}.

Write $u_j=v_j/\sqrt{\eta_j}$ ; these directions are $A$ -orthonormal. The full remaining covariance and its chronological $d$ -term prefix are

B_m=\sum_{j=m+1}^{n}c_ju_ju_j^{\mathsf T}, \qquad B_{m,d}=\sum_{j=m+1}^{m+d}c_ju_ju_j^{\mathsf T}.

For arbitrary coefficients $t_j$ ,

\left\|\sum_jt_ju_ju_j^{\mathsf T}\right\|_{A,A^{-1}} =\left\|\sum_jt_j(A^{1/2}u_j)(A^{1/2}u_j)^{\mathsf T}\right\|_2 =\max_j|t_j|.

Thus every proper prefix $1\le d<n-m$ satisfies

\|B_m-B_{m,d}\|_{A,A^{-1}}=c_n=a^{2n-2}.

But retaining only the final direction is already a better rank-one approximation:

\left\|B_m-c_nu_nu_n^{\mathsf T}\right\|_{A,A^{-1}} =c_{n-1}=a^{2n-4}<c_n.

In fact the optimal rank- $d$ error is $c_{n-d}$ , so the chronological-prefix error exceeds the optimum by the exact factor $a^{2d}$ . At $m=1$ , optimality requires the full tail $d=n-1$ ; no short prefix works.

More generally, every prescribed positive profile $c_1,\ldots,c_n$ occurs: take

L=I_n+\sum_{j=1}^{n-1}\sqrt{\frac{c_{j+1}}{c_j}}\, e_{j+1}e_j^{\mathsf T}, \qquad A=LL^{\mathsf T},\qquad b=\sqrt{c_1}\,e_1.

The same Galerkin calculation gives

r_j=(-1)^j\sqrt{c_{j+1}}\,e_{j+1}, \qquad \gamma_j=1, \qquad \gamma_j\|r_{j-1}\|_2^2=c_j.

Finally, the above tridiagonal examples have no premature conjugate-gradient breakdown. All coefficients and strict inequalities vary continuously on a full-dimensional open neighborhood of $A$ within the positive-definite cone, with $b=e_1$ fixed. Strictly increasing weights therefore persist on an open set of positive Lebesgue measure. Hence the conjecture fails not merely for exceptional matrices, but on nonempty open sets in every dimension $n\ge3$ .