0
$\begingroup$

This is part-1 of a series of questions regarding (ultimately), in my implementing a co-ordinate descent algorithm, but I have broken it up into parts as I try to solve it 'by hand' first, so that I can better understand.

So basically, I am given a vector, $\begin{bmatrix} x_{1} & x_{2} & x_{3} \end{bmatrix} $, and I am trying to minimize a function of this vector, given by:

$ H(x_{1}, x_{2}, \cdots, x_{N}) = \displaystyle\sum\limits_{i=1}^N \displaystyle\sum\limits_{j=1}^N \frac{\lvert x_{i} - x_{j} \rvert^{p}}{p} $

where here obviously for the sake of simplicity, $N=3$, and I have chosen $p=2$. What this is trying to do is minimize the sum of the total absolute differences (raised to a power) of all the samples of the vector. Now, I know the answer in the end is $x_{1} = x_{2} = x_{3} = c$, where $c$ is just some constant. In other words, a flat line.

So what I did, was take the partial derivatives of $H$ as a function of $x_{1}, x_{2}$ and $x_{3}$, and set them all to 0. The final equations I come up with are:

$ 2x_{1} - x_{2} - x_{3} = 0 \\ -x_{1} + 2x_{2} -x_{3} = 0 \\ -x_{1} - x_{2} + 2x_{3} = 0 $

My questions are as follows:

  • Is this correct?

    • If so, how does one determine the fact that all x's must be equal to each other from here?
  • What would be be partial derivative equations if p = 1?

One bonus ease of implementation question:

  • Is there an easy way to show all those results in wolfram alpha for this particular case? (I am new to it, but also need a quick way to test my hand calcs through it).

Thanks in advance!

  • 0
    Hey, Wolfram [can minimize](http://www.wolframalpha.com/input/?i=+minimize+%28%7Cx+-+y%7C%5E2+%2B+%7Cx+-+z%7C%5E2+%2B+%7Cy+-+z%7C%5E2%29)2012-04-03

1 Answers 1

2

Longer than a comment

The $3$ linear equations in your questions, can be rewritten as $Ax = 0,$ i.e.: $ \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = 0 \tag{1}$ The rank of $A$ is 2. (Google: "how to compute rank of a matrix") In other words, the nullity of $A$ is $1.$ (Google: "rank+nullity theorem") The nullspace basis is (Google: "how to compute nullspace basis of a matrix"): $b = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} $ In other words, all solutions to Equation $(1)$ above, are multiples of $b.$ So $x_1 = x_2 = x_3 = c$ is a solution for any $c.$


For future references, you can ask Wolfram|Alpha for nullity and nullspace basis. You can also ask for minimization directly.

  • 0
    In Wolfram, you can ask for the [nullity](http://www.wolframalpha.com/input/?i=Nullity%28%5B%5B2%2C+-1%2C+-1%5D%2C+%5B-1%2C+2%2C+-1%5D%2C+%5B-1%2C+-1%2C+2%5D%5D%29) or the [nullspace basis](http://www.wolframalpha.com/input/?i=nullspace+basis%28%5B%5B2%2C+-1%2C+-1%5D%2C+%5B-1%2C+2%2C+-1%5D%2C+%5B-1%2C+-1%2C+2%5D%5D%29) of a matrix.2012-04-03