1
$\begingroup$

I am reading an image processing paper robust super-resolution image reconstruction. In this paper, it uses some basic knowledge from robust statistics. One fact it quotes in the paper is:

For normally distributed data, L1 norm produces an estimator with higher variance than the optimal L^2 (quadratic) norm

Could someone explain the reason? Thanks.

$\endgroup$
2
  • $\begingroup$ You're missing the most important part of that sentence: "For normally distributed data, the L1 norm produces estimates with higher variance than the optimal L2 (quadratic) norm." $\endgroup$
    – Axoren
    Dec 15, 2015 at 21:18
  • $\begingroup$ @Axoren Changed as you have suggested. Thanks. $\endgroup$
    – feelfree
    Dec 15, 2015 at 21:26

1 Answer 1

3
$\begingroup$

When normalized, normally-distributed data in $n$-dimensional space can be seen as a really fuzzy $n$-ball with a center $\vec \mu$ and a soft-boundary square-distance $\sigma_i^2$ away from the center.

You can double check this with visualization tools: Sample points from a normal distribution in two or three dimensions and watch how they form a point-cloud that looks more than vaguely like a sphere.

Because of this, the $L2$ norm works wonders. As part of the cost function, it enforces that we're trying to tightly pack a ball, with a regularizing term enforcing that we don't pack the ball too tightly.

If we use $L1$, the shape of the "ball" we're packing changes shape, it becomes a contents of a simplex. You can think of a simplex as the largest $n$-cube that is contained in an $n$-cube of same major radius. This leads to higher variance immediately since a ball in $L2$ norm is the same shape as our variance already and we're trying to pack the same data into a smaller space.

Because of the difference in shapes of the balls in these norms. We'll either be left with a lot of empty space at the corners of the simplex or a saturation of points outside of the faces of the simplex. Our error will always be larger than the $n$-ball of the the $L2$ norm which the already round data can snuggly fit inside of.

$\endgroup$
2
  • 1
    $\begingroup$ Side note: With this understanding, you can now see what it's important that you specified "normally distributed". You can construct an arbitrary dataset for which it's data conforms to the shape of a simplex and nicely fits with the $L1$ norm over the $L2$ norm. $\endgroup$
    – Axoren
    Dec 15, 2015 at 21:45
  • 1
    $\begingroup$ This is such an interesting explanation of the l1/l2 norms' relationship to the variance of an estimator.. can i ask how you developed it? what did you study to build up to this? this is a gem of an explanation. $\endgroup$ Apr 15, 2022 at 3:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .