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 working on the following problem:

Suppose we want to fit a polynomial of degree 0 $p(x)=a$ to data points $(1,0),(2,0),(3,0),(4,10)$. In the usual least squares fit we are looking for the value of $a$ which minimizes $$\left\Vert \begin{bmatrix}a\\ a\\ a\\ a \end{bmatrix}-\begin{bmatrix}0\\ 0\\ 0\\ 10 \end{bmatrix}\right\Vert $$ in the usual Euclidean norm. Compare this against the fit obtained using the 1-norm. Is the 1-norm fit more or less sensitive to outliers in the data?

I am trying to figure this out in a very general way but I'm worried my linear algebra might not be up to snuff. Anyway, I figured out that if we consider the vectors $$\mathbf{y}=\begin{bmatrix}y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{bmatrix},\mathbf{\Delta y}=\begin{bmatrix}\Delta y_{1}\\ \Delta y_{2}\\ \Delta y_{3}\\ \Delta y_{4} \end{bmatrix}$$

Where $\mathbf{\Delta y}$ is a vector of errors, then in the 2-norm we have

$$\min_{a}\left\Vert \mathbf{a-(y+\Delta y)}\right\Vert ^{2} = \min_{a}\sum_{i=1}^{4}\left[a-\left(y_{i}+\Delta y_{i}\right)\right]{}^{2} = \min_{a}\sum_{i=1}^{4}\left[a^{2}-2a(y_{i}+\Delta y_{i})+(y_{i}+\Delta y_{i})^{2}\right] = \min_{a}\left[4a^{2}-\left(2\sum_{i=1}^{4}(y_{i}+\Delta y_{i})\right)a+(y_{i}+\Delta y_{i})^{2}\right] $$

Which has a minimum at $$\frac{\sum_{i=1}^{4}(y_{i}+\Delta y_{i})}{4}$$So changing any $y_i$ to $y_i+\Delta y_i$ changes $a$ by $y_i/4$.

I don't get nearly as nice of a solution in the 1-norm though.

$$\min_{a}\left\Vert \mathbf{a-(y+\Delta y)}\right\Vert _{1}=\min_{a}\sum_{i=1}^{4}\left|a-(y_{i}+\Delta y_{i})\right|$$

I don't know exactly what I can say about the solution to this. Is there any way to pin down or put bounds on the solution to that problem?

share|improve this question
    
I have misunderstood your question, so I have deleted my answer. On a second thought, I think the question simply means that the data entry $10$ is the outlier, and it wants you to compare the two minimizers $a$ obtained with the two different norms. –  user1551 Feb 6 '13 at 11:39
    
The difficulty you have encountered in solving problems involving the $1$-norm is one of the reasons people use the $2$-norm --- it's differentiable, the $1$-norm isn't. I admire your ambition in trying to solve the general problem, but maybe it's better, at least for starters, to do the problem as given. Without the outlier, both norms would give the zero polynomial: with the outlier, which norm takes you farther from the zero polynomial? –  Gerry Myerson Feb 7 '13 at 4:26

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.