3
$\begingroup$

Let $\{v_i\}_{i=1}^N$ be a set of $n$-dimensional real vectors spanning $\mathbb{R}^n$. Let $p\in [0,1]$ be a rational number and consider the iteration \begin{equation} X_{k+1}=\frac{1}{N}\sum_{i=1}^N \frac{X_k^{p}v_i v_i^\top X_k^{p}}{v_i^\top X_k^{2p}v_i},\quad X_0=\frac{1}{n}I_n\qquad (\star) \end{equation} (Given a positive semi-definite matrix $Y$, $Y^p$, $p\in\mathbb{Q},\ p\in (0,1)$, denotes the principal matrix $p$-th root of $Y$). If we denote by $\Pi_y:=\frac{y y^\top}{y^\top y}$ the orthogonal projection onto $\mathrm{span}\{y\}$, $y\in\mathbb{R}^n$, then ($\star$) can be seen as an arithmetic mean of rank-one orthogonal projections each one projecting onto $\mathrm{span}\{X_k^p v_i\}$, namely \begin{equation} X_{k+1}=\frac{1}{N}\sum_{i=1}^N \Pi_{X_k^p v_i},\quad X_0=\frac{1}{n}I_n\qquad (\star\star) \end{equation} Notice that ($\star$) sends positive definite matrices to positive definite matrices and is trace-preserving (namely its trace is always 1).

First, I would like to know if similar algorithms have been studied somewhere in the literature. In particular, I would be interested in the convergence properties of ($\star$). Note that, since ($\star$) maps trace-one positive definite matrices to trace-one positive definite matrices and is continuous, by Browuer's fixed point theorem it admits (at least) one fixed point. However, what about uniqueness and attractivity of the fixed point?

I list below other (perhaps naïve) considerations and some further comments on the algorithm ($\star$).

  1. For $p=0$, the iteration clearly converges in one step to the (positive definite) arithmetic mean of the set of projections $\{\Pi_{v_i}\}_{i=1}^N$.

  2. For $p=1$, extensive simulations seem to suggest that the algorithm converges to a rank-one orthogonal projection (except when we pick a set of orthogonal vectors $\{v_i\}_{i=1}^N$, in which case the iteration stays fixed at $\frac{1}{n}I_n$).

  3. For $0<p<1$, simulations seem to suggest that the algorithm converges to a positive definite matrix and the lower the value of $p$ the closer is the latter matrix to the arithmetic mean of $\{\Pi_{v_i}\}_{i=1}^N$.

Relying on the above considerations and on numerical evidences, my conjecture is that for $p<1$ there is a kind of "antagonistic action" of the matrix $p$-th root which pushes the iteration towards the the arithmetic mean of $\{\Pi_{v_i}\}_{i=1}^N$, while for $p=1$ this action disappears and the algorithm converges to an orthogonal rank-1 projection. Furthermore, my guess is that, if I will be able to prove convergence for the case $p=1$, then by a sort of continuity argument on the parameter $p$, I will also be able to prove convergence for $0<p<1$.

I've been at this problem for some time, with no further progress. Thus I really appreciate to hear your opinions/comments/criticisms. Thanks a lot.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ This looks like the iteration has been derived by trying to solve $\nabla \Phi=0$; could you write down the original problem? We studied several such iterations previously, maybe one of them might be helpful to you, e.g., please have a look at: arxiv.org/pdf/1410.4812v2.pdf $\endgroup$
    – Suvrit
    Commented Feb 21, 2016 at 14:15
  • 1
    $\begingroup$ @Suvrit: I've read your paper and I found it very interesting! Moreover, the iteration (3.8) seems to be the “regularized” version of mine! Hence, I wonder if I can use an argument similar to that used in Sec 3.1 to prove convergence of my iteration for $p=1/2$ (perhaps, replacing $I$ by $\varepsilon I$ and letting $\varepsilon\to 0$?). I think that one issue is that Lemma 3 doesn't hold anymore and this implies that my iteration can tend to a singular matrix (rank-1 projection, actually). However, I know that my iteration always admits a positive-definite fixed point and maybe this can help. $\endgroup$
    – Ludwig
    Commented Mar 1, 2016 at 10:31
  • 1
    $\begingroup$ Did you check if an argument similar to that for (3.10) works out in your case? $\endgroup$
    – Suvrit
    Commented Mar 1, 2016 at 20:37
  • 1
    $\begingroup$ Yes, using an $\epsilon I$ perturbation and letting $\epsilon \to 0$ in (3.8) will "work" except for the one troublesome thing of ensuring that the limit is strictly positive definite.... $\endgroup$
    – Suvrit
    Commented Mar 2, 2016 at 15:59
  • 1
    $\begingroup$ What I meant in my first comment was: consider minimization of $$\phi(X) = \text{trace}(X) - \sum_i \log(v_i^TXv_i).$$ This is strictly convex on $X \succ 0$. Thus, if $\nabla \phi(X)=0$ has a solution, it will be unique. Using Brouwer, you claimed existence (though am not sure about it because you need to also establish a compact set within which the iteration lives)....cont'd $\endgroup$
    – Suvrit
    Commented Mar 5, 2016 at 22:40

0

Reset to default

You must log in to answer this question.