2
$\begingroup$

I am trying to minimize the following function $$ \min_{a \in \mathbb{R}^n} \frac{1}{n}(Ka-y)^T(Ka-y) + \lambda a^TKa $$ where $K$ is a positive semi-definite matrix. Since the first part and the second part is convex, the whole function is convex. Then taking derivative and equating to zero I get $$ K((K+\lambda nI)a-y)=0 $$

$\textbf{My main question}$ is from here, how can I get a solution for $a$?

I suspect that the nullspace of $K$ is not only zero. So I cannot directly write $$ (K+\lambda nI)a-y=0 $$

$\textbf{My second question}$ is even if I could write it, how can I be sure that the matrix $K+\lambda n I$ is invertible?

$\endgroup$
2
  • 1
    $\begingroup$ Indeed, if $K$ is only assumed to be semidefinite, its nullspace can very well be nontrivial. For $\lambda>0$, the matrix $K+\lambda nI$ is positive and definite, hence invertible. $\endgroup$
    – Julien
    Feb 10 '13 at 15:51
  • 2
    $\begingroup$ $K$ is positive semi-definite and $\lambda n I$ is strictly positive definite if $\lambda > 0$, so $K+\lambda n I$ is strictly positive definite and thus invertible. $\endgroup$
    – JACKY Li
    Feb 10 '13 at 16:54
1
$\begingroup$

As mentioned in the comments, $K+\lambda n I$ is positive-definite and hence invertible.

This is because if $A$ is any e.g. real matrix, then for any $\epsilon \in \mathbb{R}$, the eigenvalues of $A+\epsilon I$ are those of $A$ with $\epsilon$ added to them. Proof: Let $(A+\epsilon I)x=\tilde{\lambda} x$. Then $Ax = (\tilde{\lambda}-\epsilon)x$ and thus $\tilde{\lambda}-\epsilon$ must be an eigenvalue of $A$. Thus $(\lambda,x)$ is an eigenpair of $A$ if and only if $(\lambda+\epsilon,x)$ is an eigenpair of $A+\epsilon I$. I leave the converse statement to you.

In particular, if $K$ is positive-semidefinite, then all its eigenvalues are non-negative. Since $\lambda n >0$, then the eigenvalues of the regularized matrix $K + \lambda n I$ will be at least $\lambda n$. Hence $K + \lambda n I$ will be positive-definite.

When we have $K ((K+\lambda nI) \alpha -y)=0$, that means that the vector $(K+\lambda nI) \alpha -y$ must lie inside the nullspace of $K$. Since $0$ is inside the nullspace of $K$, we can try to enforce the equality $(K+\lambda nI) \alpha -y=0$, which admits a solution, since $(K+\lambda nI)$ is invertible. In fact, for any vector $\xi$ inside the nullspace of $K$ the equation $(K+\lambda nI) \alpha -y=\xi$ always admits a solution. Hence the set of solutions is $\left\{(K+\lambda nI)^{-1}(y+\xi): \xi \in \mathcal{N}(K) \right\}$.

$\endgroup$
4
  • $\begingroup$ thanks. but my main question was how can I pass from eq.2 to eq.3? May I write $(K+\lambda nI)a-y=0$ from $K((K+\lambda nI)a-y)=0$ $\endgroup$
    – neticin
    Feb 10 '13 at 21:12
  • $\begingroup$ I added some explanation on that. $\endgroup$
    – Manos
    Feb 11 '13 at 5:14
  • $\begingroup$ so here, we found only one solution for $a$. there may be other solutions as well, right? $\endgroup$
    – neticin
    Feb 11 '13 at 10:28
  • $\begingroup$ Correct. I added the complete solution. $\endgroup$
    – Manos
    Feb 11 '13 at 14:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.