Talks given at NuHAG events

Four-step Basis Pursuit with Applications

  Vitezslav Vesely

  given at  strobl07 (17.06.07)
  id:  719
  length:  min
  status:  accepted
  type:  poster
When solving real problems there is often missing a reliable theory behind
them. In such situations the ideas about a choice of an appropriate model are
very vague and produce models where it is hard to balance
the requirement on sufficient regularity of the model
(as few parameters as possible to guarantee numerical stability)
and feasible precision which forces the analyst to increase the number of
model components typically leading to overparametrization
accompanied with non-uniqueness and numerical instability of solutions.

The standard estimation algorithms use to fail due to numerical
instability caused by strong overparametrization.
In~\cite{Ves05} there was implemented
a computationally intensive sparse parameter estimation
technique based on BPA4 --- a four-step modification
of the Basis Pursuit Algorithm originally suggested
by Chen et al~\cite{CDS98} for time-scale analysis of digital
signals and utilizing numerical procedure~\cite{Sau01}.

\cite{Ves05} is a collection of functions allowing one to construct
and manipulate big finite frames in any abstract Hilbert space $\mathcal{H}$ with
arbitrarily parametrized user-defined frame atoms going far beyond
the common shift/scale/modulation schemes widely used for spectral
representation of signals.
Then BPA4 serves as a universal tool both for finding
a stable sparse frame expansion approximating any object from or outside of
$\mathcal{H}$ and possibly establishing the appropriate dual frame atoms
if necessary.

In addition to some minimal theoretical background this contribution demonstrates
performance and flexibility of BPA4 on
four problems coming from completely diverse application
fields: kernel approximation and smoothing (denoising)~\cite{ZVH04},
improved time series forecasting within an overcomplete stochastic frame
of type ARMA~\cite{VT06},
analysis of air pollution by suspended particulate matter~\cite{VTMK06}
and ROC curve estimation~\cite{MV05b}.
This new computationally intensive approach allowed us to
reliably identify nearly zero parameters in the respective model and
thus to find numerically stable sparse solutions.

{S. S.} Chen, {D. L.} Donoho, and {M. A.} Saunders.
\newblock Atomic decomposition by basis pursuit.
\newblock {\em SIAM J. Sci. Comput.}, 20(1):33--61, 1998.
\newblock reprinted in SIAM Review, {\bf 43} (2001), no. 1, pp. 129--159.

{M.~A.} Saunders.
\newblock {\it pdsco.m\/}: {MATLAB} code for minimizing convex separable
objective functions subject to \mbox{$Ax=b,x\geq 0$},
{\rm\~{}atomizer/\/}, 2001.

\newblock {\it framebox\/}: {MATLAB} toolbox for overcomplete modeling and sparse
parameter estimation, (C) 2001--2007.

J.~Zelinka, V.~Vesel\'y, and I.~Horov\'a, \emph{Comparative study of two kernel
smoothing techniques}, {Proceedings of the summer school DATASTAT'2003,
Svratka} (I.~Horov\'a, ed.), Folia Fac. Sci. Nat. Univ. Masaryk. Brunensis,
Mathematica, vol.~15, Dept. of Appl. Math., Masaryk University, Brno, Czech
Rep., 2004, pp.~419--436.

V.~Vesel\'y and J.~Tonner.
\newblock {Sparse Parameter Estimation in Overcomplete Time Series Models}.
\newblock {\em {Austrian Journal of Statistics}}, 35(2\&3): 371-378, 2006.

V.~Vesel\'y, J.~Tonner, J.~Mich\'alek, and M.~Kol\'a\v{r}, \emph{{Air pollution
analysis based on sparse estimates from an overcomplete model}}, {TIES 2006,
18-22 June 2006, Kalmar, Sweden}, 2006.

J.~Mich\'alek and V.~Vesel\'y, \emph{{Comparison of the ROC curve estimators}},
{25th European Meeting of Statisticians, 24--28 July 2005, Oslo Norway, Final
Programme and Abstracts}, University of Oslo, Norway, 2005, p.~499.

\cite{ZVH04}-\cite{MV05b} are available in electronic
form at author's web site
Research supported by M\v{S}MT
(Ministery of Education of the Czech Republic):
research contract MSM0021622418

Enter here the CODE for editing this talk:
If you have forgotten the CODE for your talk click here to send an email to the Webmaster!
NOTICE: In [EDIT-MODUS] you can also UPLOAD a presentation"