Files in this item



application/pdfGENG_QUAN.pdf (460kB)
(no description provided)PDF


Title:On the Local Correctness of L1-minimization for Dictionary Learning Algorithm
Author(s):Geng, Quan
Advisor(s):Viswanath, Pramod
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Dictionary Learning
Compressed Sensing
Abstract:The idea that many classes of signals can be represented by linear combination of a small set of atoms of a dictionary has had a great impact on various signal processing applications, e.g., image compression, super resolution imaging and robust face recognition. For practical problems such a sparsifying dictionary is usually unknown ahead of time, and many heuristics have been proposed to learn an efficient dictionary from the given data. However, there is little theory explaining the empirical success of these heuristic methods. In this work, we prove that under mild conditions, the dictionary learning problem is actually locally well-posed: the desired solution is a local optimum of the $\ell_1$-norm minimization problem. More precisely, let $\mb A \in \Re^{m \times n}$ be an incoherent (and possibly overcomplete, i.e., $m < n$) dictionary, the coefficients $\mb X \in \Re^{n \times p}$ follow a random sparse model, and $\mb Y = \mb A \mb X$ be the observed data; then with high probability $(\mb A,\mb X)$ is a local optimum of the $\ell_1$-minimization problem: \begin{equation*}\label{mainopt} \displaystyle\mathop{\mathrm{minimize}}_{\mb A',\mb X'} \; \| \mb X' \|_1 \quad \text{s.t.} \quad \mb Y = \mb A' \mb X', \; \| \mb A'_i \|_2 = 1 \; \forall \, i, \end{equation*} provided the number of samples $p = \Omega(n^3 k)$. This is the first result showing that the dictionary learning problem is locally solvable for an overcomplete dictionary. Our analysis draws on tools developed for the matrix completion problem. In particular, inspired by David Gross's golfing scheme, we derive relaxed optimality conditions and construct dual variables to certify the local optimality conditions.
Issue Date:2012-02-01
Rights Information:Copyright 2011 Quan Geng
Date Available in IDEALS:2014-02-01
Date Deposited:2011-12

This item appears in the following Collection(s)

Item Statistics