CVPR09-Tutorial

CVPR’09TutorialSparse Representation and Its Applications– Compressive Sensing Meets Machine LearningYi Ma, John Wright Allen Y. YangDepartment of ECE Department of EECSUniversity of Illinois University of California, Berkeleyfyima,jnwrightg@illinois.edu yang@eecs.berkeley.eduTel: 217-244-0871, Fax: 217-244-2352 Tel: 510-643-5798, Fax: 510-643-23561 ProgramDescriptionIn the past several years, there have been exciting breakthroughs in the study ofsparse representation of high-dimensional signals. That is, a signal is representedas a linear combination of relatively few base elements in an over-complete dic-tionary. Much of the excitement centers around the discovery that a sufficientlysparse linear representation can be correctly and efficiently computed by convex0 1optimization (i.e. the‘ =‘ equivalence) or greedy algorithms, even though thisproblem is extremely difficult (NP-hard) in the general case. If this was not surpris-ing enough, further studies have shown that such high-dimensional sparse signalscan be accurately recovered from drastically smaller number of (even randomlyselected) linear measurements, hence the catch phrase “compressive sensing” orsometimes, “compressed sensing.”These results have already caused a small revolution in the community of sta-tistical signal processing as they provide entirely new perspectives to some of thefundamental principles and doctrines in signal processing such as the samplingbounds and the choice of ...