BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Applied and Computational Analysis
SUMMARY:Numerical properties of solutions of lasso regress
ion - Joab Winkler (University of Sheffield)
DTSTART;TZID=Europe/London:20231116T150000
DTEND;TZID=Europe/London:20231116T160000
UID:TALK207415AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/207415
DESCRIPTION:The determination of a concise model of a linear s
ystem when there are fewer samples m than predicto
rs n requires the solution of the equation Ax = b
where A∈R^m×n^ and rank A = m\, such that the sele
cted solution from the infinite set of solutions i
s sparse\, that is\, many of its components are ze
ro. This leads to the minimisation with respect to
x of f(x\,λ) = ||Ax-b||^2^_2+ λ||x||_2\, where λ
is the regularisation parameter. This problem\, wh
ich is called lasso regression\, is more difficult
than Tikhonov regularisation because there does n
ot exist a 1-norm matrix decomposition and the 1-n
orm of a vector or matrix is not a differentiable
function.\nLasso regression yields a family of fun
ctions xlasso(λ) and it is necessary to determine
the optimal value of λ\, that is\, the value of λ
that balances the fidelity of the model\, ||A xlas
so(λ)-b||≈0\, and the satisfaction of the constrai
nt that xlasso(λ) be sparse. A solution that satis
fies both these conditions\, that is\, the objecti
ve function and the constraint assume\, approximat
ely\, their minimum values is called an optimal sp
arse solution. In particular\, a sparse solution e
xists for many values of λ\, but the restriction o
f interest to an optimal sparse solution places re
strictions on λ\, A and b.\nIt is shown that there
does not exist an optimal sparse solution when th
e least squares (LS) solution xls = A^†^b = A^T^(A
A^T^)^-1^b is well conditioned. It is also shown t
hat\, by contrast\, an optimal sparse solution tha
t has few zero entries exists if xls is ill condit
ioned. This association between sparsity and numer
ical stability has been observed in feature select
ion and the analysis of fMRI images of the brain.
The relationship between the numerical condition o
f the LS problem and the existence of an optimal s
parse solution requires that a refined condition n
umber of xls be developed because it cannot be obt
ained from the condition number κ(A) of A. This in
adequacy of κ(A) follows because it is a function
of A only\, but xls is a function of A and b.\nThe
optimal value of λ is usually computed by cross v
alidation (CV)\, but it is problematic because it
requires the determination of a shallow minimum of
a function. A better method\, which requires the
computation of the coordinates of the corner of a
curve that has the form of an L\, is described and
examples that demonstrate its superiority with re
spect to CV are presented.\nThe talk includes exam
ples of well conditioned and ill conditioned solut
ions xls of the LS problem that do\, and do not\,
possess an optimal sparse solution. The examples i
nclude the effect of noise on the results obtained
by the L-curve and CV.
LOCATION:Centre for Mathematical Sciences\, MR14
CONTACT:Nicolas Boulle
END:VEVENT
END:VCALENDAR