Dictionary Learning with Convex Update (ROMD)
  Dictionary learning aims to find a dictionary under which the training data
can be sparsely represented, and it is usually achieved by iteratively applying
two stages: sparse coding and dictionary update. Typical methods for dictionary
update focuses on refining both dictionary atoms and their corresponding sparse
coefficients by using the sparsity patterns obtained from sparse coding stage,
and hence it is a non-convex bilinear inverse problem. In this paper, we
propose a Rank-One Matrix Decomposition (ROMD) algorithm to recast this
challenge into a convex problem by resolving these two variables into a set of
rank-one matrices. Different from methods in the literature, ROMD updates the
whole dictionary at a time using convex programming. The advantages hence
include both convergence guarantees for dictionary update and faster
convergence of the whole dictionary learning. The performance of ROMD is
compared with other benchmark dictionary learning algorithms. The results show
the improvement of ROMD in recovery accuracy, especially in the cases of high
sparsity level and fewer observation data.
