Re: [R] total variation penalty

From: roger koenker <>
Date: Thu 03 Mar 2005 - 13:30:26 EST

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


     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

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

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


     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 
                neural network models}

     Author = {Fan, Jianqing and Li, Runze},
     Title = {Variable Selection Via Nonconcave Penalized Likelihood and 
             Oracle Properties},
     Year = 2001,
     Journal = {Journal of the American Statistical Association},
     Volume = 96,
     Number = 456,
     Pages = {1348--1360},

> 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:


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



         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: Roger Koenker
> email Department of Economics
> vox: 217-333-4558 University of Illinois
> fax: 217-244-6678 Champaign, IL 61820 mailing list PLEASE do read the posting guide! Received on Thu Mar 03 13:49:14 2005

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:30:39 EST