BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Numerical properties of solutions of lasso regression - Joab Winkl
 er (University of Sheffield)
DTSTART:20231116T150000Z
DTEND:20231116T160000Z
UID:TALK207415@talks.cam.ac.uk
CONTACT:Nicolas Boulle
DESCRIPTION:The determination of a concise model of a linear system when t
 here are fewer samples m than predictors n requires the solution of the eq
 uation Ax = b where A∈R^m×n^ and rank A = m\, such that the selected so
 lution from the infinite set of solutions is sparse\, that is\, many of it
 s components are zero. This leads to the minimisation with respect to x of
  f(x\,λ) = ||Ax-b||^2^_2+ λ||x||_2\, where λ is the regularisation para
 meter. This problem\, which is called lasso regression\, is more difficult
  than Tikhonov regularisation because there does not exist a 1-norm matrix
  decomposition and the 1-norm of a vector or matrix is not a differentiabl
 e function.\nLasso regression yields a family of functions xlasso(λ) and 
 it is necessary to determine the optimal value of λ\, that is\, the value
  of λ that balances the fidelity of the model\, ||A xlasso(λ)-b||≈0\, 
 and the satisfaction of the constraint that xlasso(λ) be sparse. A soluti
 on that satisfies both these conditions\, that is\, the objective function
  and the constraint assume\, approximately\, their minimum values is calle
 d an optimal sparse solution. In particular\, a sparse solution exists for
  many values of λ\, but the restriction of interest to an optimal sparse 
 solution places restrictions on λ\, A and b.\nIt is shown that there does
  not exist an optimal sparse solution when the least squares (LS) solution
  xls = A^†^b = A^T^(AA^T^)^-1^b is well conditioned. It is also shown th
 at\, by contrast\, an optimal sparse solution that has few zero entries ex
 ists if xls is ill conditioned. This association between sparsity and nume
 rical stability has been observed in feature selection and the analysis of
  fMRI images of the brain. The relationship between the numerical conditio
 n of the LS problem and the existence of an optimal sparse solution requir
 es that a refined condition number of xls be developed because it cannot b
 e obtained from the condition number κ(A) of A. This inadequacy of κ(A) 
 follows because it is a function of A only\, but xls is a function of A an
 d b.\nThe optimal value of λ is usually computed by cross validation (CV)
 \, but it is problematic because it requires the determination of a shallo
 w 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 respect to C
 V are presented.\nThe talk includes examples of well conditioned and ill c
 onditioned solutions xls of the LS problem that do\, and do not\, possess 
 an optimal sparse solution. The examples include the effect of noise on th
 e results obtained by the L-curve and CV.
LOCATION:Centre for Mathematical Sciences\, MR14
END:VEVENT
END:VCALENDAR