6
$\begingroup$

Suppose we are given a set of symmetric, positive definite matrices $A_1,A_2,\ldots,A_k\in\mathbb{R}^{n\times n}$. Is there any numerical method or reduction to a known problem (e.g. eigenvalue computation) that can solve the following problem?

$$ \begin{array}{rl} \min_{v_1,\ldots,v_k\in\mathbb{R}^n} & \sum_{i=1}^kv_i^\top A_iv_i\\ \textrm{subject to }&v_i^\top v_j=\delta_{[i=j]}. \end{array} $$

Note: The problem has some resemblance to the "joint diagonalization" problem, e.g. in this paper. The difference seems to be that in joint diagonalization you use the same basis to diagonalize multiple matrices.

Note 2: If the $A_i$'s do not have the same eigenvectors, then the $v_i$'s will not be exactly eigenvectors of the $A_i$'s.

Note 3: My intuition is that this will give a set of mutually orthonormal vectors $v_1,\ldots,v_k\in\mathbb{R}^n$, with the property that vector $v_i$ is similar to an eigenvector of $A_i$. But this is not an eigenvalue problem.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Would you add a few words about the desired properties of $v_i$? In particular, how strong is the property "looks like an eigenvector" compared with "is an eigenvector?" $\endgroup$ – Carl Christian Oct 7 '17 at 23:13
  • $\begingroup$ I think asking that the $v_i$'s are mutually orthogonal will prevent them from actually being eigenvectors of the individual $A_i$'s, which may have different eigenspaces. For a single $A$ by itself, I'd compute the lowest-eigenvalue eigenvector. So the formulation in my post is essentially an extension of the Rayleigh quotient formulation of eigenproblems. Does that make sense? $\endgroup$ – Justin Solomon Oct 8 '17 at 4:00
  • 1
    $\begingroup$ @JustinSolomon Still, could you reword the question please? I found it confusing too. It's clear from comments that you want to solve this specific optimization problem. But you also say "in particular, consider..." (less ambiguous than before), which makes it sound like the optimization problem is just one of possible precise problems (and not necessarily the only one) that correspond to the informal description up above, hence the question seems ambiguous even though you think it's not. The relationship between "looks like an eigenvector" and the Rayleigh quotients could be more explicit too $\endgroup$ – Kirill Oct 8 '17 at 23:13
  • $\begingroup$ Rephrased to remove mention of eigenvector altogether --- apparently my intuition is causing confusion. $\endgroup$ – Justin Solomon Oct 9 '17 at 0:48
  • $\begingroup$ (I think it's perfectly clear now; my comment no longer matters.) Could this be a counterexample to your intuition maybe? Take $k=n=2$, $A_1 = I$, $A_2 = [1,\epsilon;\epsilon,1-\delta]$ (perturbation of $I$), then $v_1=(\cos\theta,\sin\theta)$ with $\theta = \frac12\arctan(2\epsilon/\delta)+\pi\mathbb{Z}$, which can be made anything while keeping $\epsilon,\delta$ small. But I'm guessing your $A$'s aren't truly arbitrary, so maybe not. $\endgroup$ – Kirill Oct 9 '17 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.