In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties – the ability to adapt to specific signal data and a fast implementation of the dictionary. To sparsely represent signals residing on weighted graphs, an additional design challenge is to incorporate the intrinsic geometric structure of the irregular data domain into the atoms of the dictionary. In this work, we propose a parametric dictionary learning algorithm to design data-adapted, structured dictionaries that sparsely represent graph signals. In particular, we model graph signals as combinations of overlapping local patterns. We impose the constraint that each dictionary is a concatenation of subdictionaries, with each subdictionary being a polynomial of the graph Laplacian matrix, representing a single pattern translated to different areas of the graph. The learning algorithm adapts the patterns to a training set of graph signals. Experimental results on both synthetic and real datasets demonstrate that the dictionaries learned by the proposed algorithm are competitive with and often better than unstructured dictionaries learned by state-of-the-art numerical learning algorithms in terms of sparse approximation of graph signals. In contrast to the unstructured dictionaries, however, the dictionaries learned by the proposed algorithm feature localized atoms and can be implemented in a computationally efficient manner in signal processing tasks such as compression, denoising, and classification.
Finally, we remark that the graph structure is taken into consideration in @cite_21 , not explicitly into the dictionary but rather in the sparse coding coefficients. The authors use the graph Laplacian operator as a regularizer in order to impose that the obtained sparse coding coefficients vary smoothly along the geodesics of the manifold that is captured by the graph. However, the obtained dictionary does not have any particular structure. None of the previous works are able to design dictionaries that provide sparse representations, particularly adapted to a given class of graph signals, and have efficient implementations. This is exactly the objective of our work, where a structured graph signal dictionary is composed of multiple polynomial matrix functions of the graph Laplacian.
@cite_21
2124543570 2140245639 2009226074 2142940228
We propose a method for learning dictionaries towards sparse approximation of signals defined on vertices of arbitrary graphs. Dictionaries are expected to describe effectively the main spatial and spectral components of the signals of interest, so that their structure is dependent on the graph information and its spectral representation. We first show how operators can be defined for capturing different spectral components of signals on graphs. We then propose a dictionary learning algorithm built on a sparse approximation step and a dictionary update function, which iteratively leads to adapting the structured dictionary to the class of target signals. Experimental results on synthetic and natural signals on graphs demonstrate the efficiency of the proposed algorithm both in terms of sparse approximation and support recovery performance. Sparse coding has received an increasing amount of interest in recent years. It is an unsupervised learning algorithm, which finds a basis set capturing high-level semantics in the data and learns sparse coordinates in terms of the basis set. Originally applied to modeling the human visual cortex, sparse coding has been shown useful for many applications. However, most of the existing approaches to sparse coding fail to consider the geometrical structure of the data space. In many real applications, the data is more likely to reside on a low-dimensional submanifold embedded in the high-dimensional ambient space. It has been shown that the geometrical information of the data is important for discrimination. In this paper, we propose a graph based algorithm, called graph regularized sparse coding, to learn the sparse representations that explicitly take into account the local manifold structure of the data. By using graph Laplacian as a smooth operator, the obtained sparse representations vary smoothly along the geodesics of the data manifold. The extensive experimental results on image classification and clustering have demonstrated the effectiveness of our proposed algorithm. Manifold regularized sparse coding shows promising performance for various applications. The key issue that must be considered in the application is how to adaptively select the suitable graph hyper-parameters in manifold learning for the sparse coding task. Usually, cross validation is applied, but it does not necessarily scale up and easily leads to overfitting. In this article, multiple graph sparse coding (MGrSc) and multiple Hypergraph sparse coding (MHGrSc) for image representation are proposed. Inspired by the Ensemble Manifold Regularizer, we formulate multiple graph and multiple Hypergraph regularizers to guarantee the smoothness of sparse codes along the geodesics of a data manifold, which is characterized by fusing the multiple previously given graph Laplacians or Hypergraph Laplacians. Then, the proposed regularziers, respectively, are incorporated into the traditional sparse coding framework, which results in two unified objective functions of sparse coding. Alternating optimization is used to optimize the objective functions, and two, novel manifold regularized sparse coding algorithms are presented. The proposed two sparse coding methods learn both the composite manifold and the sparse coding jointly, and it is fully automatic for learning the graph hyper-parameters in the manifold learning. Image clustering tests on real world datasets demonstrated that the proposed sparse coding methods are superior to the state-of-the-art methods. Algorithms for data-driven learning of domain-specific overcomplete dictionaries are developed to obtain maximum likelihood and maximum a posteriori dictionary estimates based on the use of Bayesian models with concave Schur-concave (CSC) negative log priors. Such priors are appropriate for obtaining sparse representations of environmental signals within an appropriately chosen (environmentally matched) dictionary. The elements of the dictionary can be interpreted as concepts, features, or words capable of succinct expression of events encountered in the environment (the source of the measured signals). This is a generalization of vector quantization in that one is interested in a description involving a few dictionary entries (the proverbial "25 words or less"), but not necessarily as succinct as one entry. To learn an environmentally adapted dictionary capable of concise expression of signals generated by the environment, we develop algorithms that iterate between a representative set of sparse representations found by variants of FOCUSS and an update of the dictionary using these sparse representations.Experiments were performed using synthetic data and natural images. For complete dictionaries, we demonstrate that our algorithms have improved performance over other independent component analysis (ICA) methods, measured in terms of signal-to-noise ratios of separated sources. In the overcomplete case, we show that the true underlying dictionary and sparse sources can be accurately recovered. In tests with natural images, learned overcomplete dictionaries are shown to have higher coding efficiency than complete dictionaries; that is, images encoded with an overcomplete dictionary have both higher compression (fewer bits per pixel) and higher accuracy (lower mean square error).