R help - Mar 2005 - total variation penalty

Hi,
 
I was recently plowing through the docs of the quantreg package by Roger
Koenker and came across the total variation penalty approach to
1-dimensional spline fitting. I googled around a bit and have found some
papers originated in the image processing community, but (apart from
Roger's papers) no paper that would discuss its statistical aspects.
 
I have a couple of questions in this regard:
* Is it more natural to consider the total variation penalty in the
context of quantile regression than in the context of OLS? 
* Could someone please point to a good overview paper on the subject?
Ideally something that compares merits of different penalty functions.
 
Threre seems to be an ongoing effort to generalize this approach to 2d,
but at this time I am more interested in 1-d smoothing.
 
Thanks,
Vadim

	[[alternative HTML version deleted]]

On Mar 2, 2005, at 6:25 PM, Vadim Ogranovich wrote:
>
> I was recently plowing through the docs of the quantreg package by 
> Roger
> Koenker and came across the total variation penalty approach to
> 1-dimensional spline fitting. I googled around a bit and have found 
> some
> papers originated in the image processing community, but (apart from
> Roger's papers) no paper that would discuss its statistical aspects.
You might look at

@article{davi:kova:2001,
     Author = {Davies, P. L. and Kovac, A.},
     Title = {Local Extremes, Runs, Strings and Multiresolution},
     Year = 2001,
     Journal = {The Annals of Statistics},
     Volume = 29,
     Number = 1,
     Pages = {1--65},
     Keywords = {[62G07 (MSC2000)]; [65D10 (MSC2000)]; [62G20 (MSC2000)];
                [nonparametric regression]; [local extremes]; [runs];
                [strings]; [multiresolution analysis]; [asymptotics];
                [outliers]; [low power peaks]; nonparametric function
                estimation}
}
They are using total variation of the function rather than total 
variation of its derivative
as in the KNP paper mentioned below, but there are close connections 
between the
methods.

There are several recent  papers on what Tibshirani calls the lasso vs 
other penalties for
regression problems... for example:

@article{knig:fu:2000,
     Author = {Knight, Keith and Fu, Wenjiang},
     Title = {Asymptotics for Lasso-type Estimators},
     Year = 2000,
     Journal = {The Annals of Statistics},
     Volume = 28,
     Number = 5,
     Pages = {1356--1378},
     Keywords = {[62J05 (MSC1991)]; [62J07 (MSC1991)]; [62E20 (MSC1991)];
                [60F05 (MSC1991)]; [Penalized regression]; [Lasso];
                [shrinkage estimation]; [epi-convergence in 
distribution];
                neural network models}
}
@article{fan:li:2001,
     Author = {Fan, Jianqing and Li, Runze},
     Title = {Variable Selection Via Nonconcave Penalized Likelihood and 
Its
             Oracle Properties},
     Year = 2001,
     Journal = {Journal of the American Statistical Association},
     Volume = 96,
     Number = 456,
     Pages = {1348--1360},
     Keywords = {[HARD THRESHOLDING]; [LASSO]; [NONNEGATIVE GARROTE];
                [PENALIZED LIKELIHOOD]; [ORACLE ESTIMATOR]; [SCAD]; [SOFT

>
> I have a couple of questions in this regard:
> * Is it more natural to consider the total variation penalty in the
> context of quantile regression than in the context of OLS?
Not especially, see the lasso literature which is predominantly based
on Gaussian likelihood.  The taut string idea is also based on Gaussian
fidelity, at least in its original form.  There are some computational
conveniences involved in using l1 penalties with l1 fidelities, but with
the development of modern interior point algorithms, l1 vs l2 fidelity 
isn't really
much of a distinction.  The real question is:  do you believe in that 
old
time religion, do you have that Gaussian faith?  I don't.
> * Could someone please point to a good overview paper on the subject?
> Ideally something that compares merits of different penalty functions.
See above....
>
> Threre seems to be an ongoing effort to generalize this approach to 2d,
> but at this time I am more interested in 1-d smoothing.
>
For the sake of completeness, the additive model component of quantreg 
is
based primarily on the following two papers:


@article{koen:ng:port:1994,
     Author = {Koenker, Roger and Ng, Pin and Portnoy, Stephen},
     Title = {Quantile Smoothing Splines},
     Year = 1994,
     Journal = {Biometrika},
     Volume = 81,
     Pages = {673--680}
}

@article{KM.04,
         Author = {Koenker, R. and I. Mizera},
         Title = {Penalized Triograms:  Total Variation Regularization 
for Bivariate Smoothing},
         Journal = JRSS-B,
         Volume = 66,
         Pages = {145--163},
         Year = 2004
}
> url:    www.econ.uiuc.edu/~roger                Roger Koenker
> email   rkoenker at uiuc.edu                       Department of Economics
> vox:    217-333-4558                            University of Illinois
> fax:    217-244-6678                            Champaign, IL 61820