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 new to vector derivatives and trying to figure out a lot for my Machine Learning course. I have given the following:

$x \in \mathbb{R}^n$, $y \in \mathbb{R}^d$, $A \in \mathbb{R}^{d \times n}$,

Let $B$ be symmetric (and pos.def.). What is the minimum of

$$(Ax -y)^T (Ax -y) + x^T Bx$$

with respect to $x$?

How can I approach this problem? I have no clue yet, however, I figured out, that $(Ax -y)^T (Ax -y) + x^T Bx \in \mathbb{R}^1$, thus a real number, isn't it? Hence $B \in \mathbb{R}^{n \times n}$

I looked up some derivation rules and I've got the following:

$$\frac{\partial}{\partial x} (Ax -y)^T (Ax -y) + x^T Bx = 2A^T (Ax - y) + (B + B^T) \cdot x$$

Setting $2A^T (Ax - y) + (B + B^T) \cdot x$ to $0$:

\begin{align*} 0 & = 2A^T (Ax - y) + (B + B^T) \cdot x\\ 0 & = 2A^T A x - A^T y + (B + B^T) \cdot x\\ A^T y & = 2A^T A x + (B + B^T) \cdot x\\ (B + B^T)^{-1} \cdot A^T y & = 2A^T A x + x\\ \end{align*}

and here I am some what stuck, however, I don't know if this is the right approach

share|improve this question
    
Minimum with respect to which argument? –  Did Apr 15 '12 at 15:50
    
@Didier I have no clue, its just the minimum of the whole term. –  Mahoni Apr 15 '12 at 15:51
    
Most likely it's not the minimum with respect to both $x$ and $y$; since both terms are non-negative, that would trivially be at $x=y=0$. It seems more likely that this is a sum of two cost functions, one measuring the error in solving $Ax=y$ and the other an additional quadratic cost; if so, the task would be to find the minimum with respect to $x$. (The minimum with respect to $y$ is also trivial, $y=Ax$.) –  joriki Apr 15 '12 at 15:55
    
But what does this have to do with vector derivatives? I thought this has at least to be applied. –  Mahoni Apr 15 '12 at 15:59
1  
No clue?? So you want people to tell you what is the question that you are asking? (I am wondering: is this the exact formulation of your homework?) –  Did Apr 15 '12 at 16:13

1 Answer 1

You are good until the previous-to-last equation, which reads $A^Ty=2A^TAx+(B+B^T)x$, that is $A^Ty=Cx$ where $C$ is the matrix $C=2A^TA+B+B^T$. Hence, if $C$ is invertible, $$ x=C^{-1}A^Ty. $$ To show that $C$ is invertible, note that $C$ is symmetric hence it is enough to show that the associated quadratic form is definite positive, that is, that $z^TCz\gt0$ for every $z\ne0$. Now, $$z^TCz=2z^TA^TAz+z^TBz+z^TB^Tz=2\|Az\|^2+2z^TBz\geqslant2z^TBz, $$ and, by hypothesis, $B$ is definite positive hence $z^TBz\gt0$ for every $z\ne0$, which ends the proof.

share|improve this answer

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.