Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSupervised Linear Regression for Graph Learning from Graph Signals
140
0
0.0
(
0
)
Added by
Arun Venkitaraman
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a supervised learning approach for predicting an underlying graph from a set of graph signals. Our approach is based on linear regression. In the linear regression model, we predict edge-weights of a graph as the output, given a set of signal values on nodes of the graph as the input. We solve for the optimal regression coefficients using a relevant optimization problem that is convex and uses a graph-Laplacian based regularization. The regularization helps to promote a specific graph spectral profile of the graph signals. Simulation experiments demonstrate that our approach predicts well even in presence of outliers in input data.
rate research
Read More
The emerging field of signal processing on graph plays a more and more important role in processing signals and information related to networks. Existing works have shown that under certain conditions a smooth graph signal can be uniquely reconstructed from its decimation, i.e., data associated with a subset of vertices. However, in some potential applications (e.g., sensor networks with clustering structure), the obtained data may be a combination of signals associated with several vertices, rather than the decimation. In this paper, we propose a new concept of local measurement, which is a generalization of decimation. Using the local measurements, a local-set-based method named iterative local measurement reconstruction (ILMR) is proposed to reconstruct bandlimited graph signals. It is proved that ILMR can reconstruct the original signal perfectly under certain conditions. The performance of ILMR against noise is theoretically analyzed. The optimal choice of local weights and a greedy algorithm of local set partition are given in the sense of minimizing the expected reconstruction error. Compared with decimation, the proposed local measurement sampling and reconstruction scheme is more robust in noise existing scenarios.
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.
This paper introduces a novel graph signal processing framework for building graph-based models from classes of filtered signals. In our framework, graph-based modeling is formulated as a graph system identification problem, where the goal is to learn a weighted graph (a graph Laplacian matrix) and a graph-based filter (a function of graph Laplacian matrices). In order to solve the proposed problem, an algorithm is developed to jointly identify a graph and a graph-based filter (GBF) from multiple signal/data observations. Our algorithm is valid under the assumption that GBFs are one-to-one functions. The proposed approach can be applied to learn diffusion (heat) kernels, which are popular in various fields for modeling diffusion processes. In addition, for specific choices of graph-based filters, the proposed problem reduces to a graph Laplacian estimation problem. Our experimental results demonstrate that the proposed algorithm outperforms the current state-of-the-art methods. We also implement our framework on a real climate dataset for modeling of temperature signals.
This paper studies the problem of recovering a structured signal from a relatively small number of corrupted non-linear measurements. Assuming that signal and corruption are contained in some structure-promoted set, we suggest an extended Lasso to disentangle signal and corruption. We also provide conditions under which this recovery procedure can successfully reconstruct both signal and corruption.
We study a structured variant of the multi-armed bandit problem specified by a set of Bernoulli distributions $ u != !( u_{a,b})_{a in mathcal{A}, b in mathcal{B}}$ with means $(mu_{a,b})_{a in mathcal{A}, b in mathcal{B}}!in![0,1]^{mathcal{A}timesmathcal{B}}$ and by a given weight matrix $omega!=! (omega_{b,b})_{b,b in mathcal{B}}$, where $ mathcal{A}$ is a finite set of arms and $ mathcal{B} $ is a finite set of users. The weight matrix $omega$ is such that for any two users $b,b!in!mathcal{B}, text{max}_{ainmathcal{A}}|mu_{a,b} !-! mu_{a,b}| !leq! omega_{b,b} $. This formulation is flexible enough to capture various situations, from highly-structured scenarios ($omega!in!{0,1}^{mathcal{B}timesmathcal{B}}$) to fully unstructured setups ($omega!equiv! 1$).We consider two scenarios depending on whether the learner chooses only the actions to sample rewards from or both users and actions. We first derive problem-dependent lower bounds on the regret for this generic graph-structure that involves a structure dependent linear programming problem. Second, we adapt to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura (2015), and introduce the IMED-GS$^star$ algorithm. Interestingly, IMED-GS$^star$ does not require computing the solution of the linear programming problem more than about $log(T)$ times after $T$ steps, while being provably asymptotically optimal. Also, unlike existing bandit strategies designed for other popular structures, IMED-GS$^star$ does not resort to an explicit forced exploration scheme and only makes use of local counts of empirical events. We finally provide numerical illustration of our results that confirm the performance of IMED-GS$^star$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
