Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  1015 Feb 10 '13 at 15:51
2  
$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. –  Patrick Li Feb 10 '13 at 16:54
add comment

1 Answer 1

up vote 1 down vote accepted

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\}$.

share|improve this answer
    
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$ –  neticin Feb 10 '13 at 21:12
    
I added some explanation on that. –  Manos Feb 11 '13 at 5:14
    
so here, we found only one solution for $a$. there may be other solutions as well, right? –  neticin Feb 11 '13 at 10:28
    
Correct. I added the complete solution. –  Manos Feb 11 '13 at 14:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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