publications

2019

1. Improving Graph Trend Filtering with Non-convex Penalties Varma, R., Lee, H., Chi, Y., and Kovačević, J. In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2019 [Abs]

   In this paper, we study the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph. We extend the graph trend filtering framework to a family of nonconvex regularizers that exhibit superior recovery performance over existing convex ones. We present theoretical results in the form of asymptotic error rates for both generic and specialized graph models. We further present an ADMM-based algorithm to solve the proposed optimization problem and analyze its convergence. Numerical performance of the proposed framework with non-convex regularizers on both synthetic and real-world data are presented for denoising, support recovery, and semi-supervised classification.

2. Smooth Signal Recovery on Product Graphs Varma, R., and Kovačević, J. In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2019 [Abs]

   Product graphs are a useful way to model richer forms of graph-structured data that can be multi-modal in nature. In this work, we study the reconstruction or estimation of smooth signals on product graphs from noisy measurements. We motivate and present representations and algorithms that exploit the inherent structure in product graphs for better and more computationally efficient recovery. These contributions stem from the key insight that smooth graph signals on product graphs can be structured as low-rank tensors. We develop and present algorithms primarily based on two approaches, the first of which is the Tucker decomposition for tensors, while the second is a flexible convex optimization formulation. We further present numerical experiments that exhibit the superior performance of these methods with respect to existing methods for smooth signal recovery on graphs.

3. Vector-Valued Graph Trend Filtering with Non-Convex Penalties Varma, Rohan, Lee, Harlin, Kovačević, Jelena, and Chi, Yuejie arXiv:1905.12692 [cs, eess, stat] 2019 [Abs]

   This work studies the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph, where the value at each node can be vector-valued. We extend the graph trend filtering framework to denoising vector-valued graph signals with a family of non-convex regularizers, which exhibit superior recovery performance over existing convex regularizers. Using an oracle inequality, we establish the statistical error rates of first-order stationary points of the proposed non-convex method for generic graphs. Furthermore, we present an ADMM-based algorithm to solve the proposed method and establish its convergence. Numerical experiments are conducted on both synthetic and real-world data for denoising, support recovery, event detection, and semi-supervised classification.

4. Passive and Active Sampling for Piecewise-Smooth Graph Signals Varma, R., and Kovacević, J. In 2019 International Conference on Sampling Theory and Applications (SampTA) 2019
5. Random Sampling for Bandlimited Signals on Product Graphs Varma, R., and Kovacević, J. In 2019 International Conference on Sampling Theory and Applications (SampTA) 2019

2018

1. Sampling Theory for Graph Signals on Product Graphs Varma, R. A., and Kovacevic, J. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) 2018 [Abs]

   In this paper, we extend the sampling theory on graphs by constructing a framework that exploits the structure in product graphs for efficient sampling and recovery of bandlimited graph signals that lie on them. Product graphs are graphs that are composed from smaller graph atoms; we motivate how this model is a flexible and useful way to model richer classes of data that can be multi-modal in nature. Previous works have established a sampling theory on graphs for bandlimited signals. Importantly, the framework achieves significant savings in both sample complexity and computational complexity.

2017

1. Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies Chen, S., Varma, R., Singh, A., and Kovačević, J. IEEE Transactions on Signal and Information Processing over Networks 2017 [Abs]

   This paper builds theoretical foundations for the recovery of a newly proposed class of smooth graph signals, approximately bandlimited graph signals, under three sampling strategies: uniform sampling, experimentally designed sampling, and active sampling. We then state minimax lower bounds on the maximum risk for the approximately bandlimited class under these three sampling strategies and show that active sampling cannot fundamentally outperform experimentally designed sampling. We propose a recovery strategy to compare uniform sampling with experimentally designed sampling. As the proposed recovery strategy lends itself well to statistical analysis, we derive the exact mean square error for each sampling strategy. To study convergence rates, we introduce two types of graphs and find that 1) the proposed recovery strategy achieves the optimal rates; and 2) the experimentally designed sampling fundamentally outperforms uniform sampling for Type-2 class of graphs. To validate our proposed recovery strategy, we test it on five specific graphs: a ring graph with k nearest neighbors, an Erdos-Rényi graph, a random geometric graph, a small-world graph, and a power-law graph and find that experimental results match the proposed theory well. This paper also presents a comprehensive explanation for when and why sampling for semi-supervised learning with graphs works.

2. Graph topology recovery for regular and irregular graphs Varma, R., Chen, S., and Kovačević, J. In 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) 2017 [Abs]

   In this paper, we study the recovery of the graph topology or structure. We first extend our previous work on graph signal recovery to present a joint graph signal and structure recovery framework. By doing this, we allow the algorithm to learn a graph structure from noisy and incomplete graph signals and recover the graph signals at the same time. In this paper, we particularly focus on the specific subproblem of graph structure learning and develop algorithms towards this problem and analyze them. We briefly study the implications when the underlying true graph structure is irregular or regular. Finally, we validate the proposed methods for both synthetic data and the real-world recovery problem of semi-supervised digit-image classification.

2016

1. A statistical perspective of sampling scores for linear regression Chen, S., Varma, R., Singh, A., and Kovačcević, J. In 2016 IEEE International Symposium on Information Theory (ISIT) 2016 [Abs]

   In this paper, we consider a statistical problem of learning a linear model from noisy samples. Existing work has focused on approximating the least squares solution by using leverage-based scores as an importance sampling distribution. However, no finite sample statistical guarantees and no computationally efficient optimal sampling strategies have been proposed. To evaluate the statistical properties of different sampling strategies, we propose a simple yet effective estimator, which is easy for theoretical analysis and is useful in multitask linear regression. We derive the exact mean square error of the proposed estimator for any given sampling scores. Based on minimizing the mean square error, we propose the optimal sampling scores for both estimator and predictor, and show that they are influenced by the noise-to-signal ratio. Numerical simulations match the theoretical analysis well.

2. Representations of piecewise smooth signals on graphs Chen, S., Varma, R., Singh, A., and Kovačević, J. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2016 [Abs]

   We study representations of piecewise-smooth signals on graphs. We first define classes for smooth, piecewise-constant, and piecewise-smooth graph signals, followed by a series of multiresolution local sets to analyze those signals by implementing a multiresolution analysis on graphs. Based on these local sets, we propose local-set-based piecewise-constant and piecewise-smooth dictionaries as graph signal representations that, in spirit, resemble the classical Haar wavelet basis and are naturally localized in both graph vertex and graph Fourier domains. Moreover, they promote sparsity when representing piecewise-smooth graph signals. In the experiments, we show that local-set-based dictionaries outperform graph Fourier domain based representations when approximating both simulated and real-world graph signals.

2015

1. Signal recovery on graphs: Random versus experimentally designed sampling Chen, S., Varma, R., Singh, A., and Kovacević, J. In 2015 International Conference on Sampling Theory and Applications (SampTA) 2015 [Abs]

   We study signal recovery on graphs based on two sampling strategies: random sampling and experimentally designed sampling. We propose a new class of smooth graph signals, called approximately bandlimited. We then propose two recovery strategies based on random sampling and experimentally designed sampling. The proposed recovery strategy based on experimentally designed sampling uses sampling scores, which is similar to the leverage scores used in the matrix approximation. We show that while both strategies are unbiased estimators for the low-frequency components, the convergence rate of experimentally designed sampling is much faster than that of random sampling when a graph is irregular1. We validate the proposed recovery strategies on three specific graphs: a ring graph, an Erdös-Rényi graph, and a star graph. The simulation results support the theoretical analysis.

2. Energy-efficient route planning for autonomous aerial vehicles based on graph signal recovery Ji, T., Chen, S., Varma, R., and Kovačević, J. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) 2015 [Abs]

   We use graph signal sampling and recovery techniques to plan routes for autonomous aerial vehicles. We propose a novel method that plans an energy-efficient flight trajectory by considering the influence of wind. We model the weather stations as nodes on a graph and model wind velocity at each station as a graph signal. We observe that the wind velocities at two close stations are similar, that is, the graph signal of wind velocities is smooth. By taking advantages of the smoothness, we only query a small fraction of it and recover the rest by using a novel graph signal recovery algorithm, which solves an optimization problem. To validate the effectiveness of the proposed method, we first demonstrate the necessity to take wind into account when planning route for autonomous aerial vehicles, and then show that the proposed method produces a reliable and energy-efficient route.

3. Spectrum-blind signal recovery on graphs Varma, R., Chen, S., and Kovačević, J. In 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) 2015 [Abs]

   We consider the problem of recovering a graph signal, sparse in the graph spectral domain from a few number of samples. In contrast to most previous work on the sampling of graph signals, the setting is “spectrum-blind” where we are unaware of the graph d support of the signal. We propose a class of spectrum-blind graph signals and study two recovery strategies based on random and experimentally designed sampling inspired by the compressed sensing paradigm. We further show sampling bounds for graphs, including Erdös-Rényi random graphs. We show that experimentally designed sampling significantly outperforms random sampling for some irregular graph families.

4. Signal recovery on graphs: Random versus experimentally designed sampling Chen, S., Varma, R., Singh, A., and Kovacević, J. In 2015 International Conference on Sampling Theory and Applications (SampTA) 2015 [Abs]

   We study signal recovery on graphs based on two sampling strategies: random sampling and experimentally designed sampling. We propose a new class of smooth graph signals, called approximately bandlimited. We then propose two recovery strategies based on random sampling and experimentally designed sampling. The proposed recovery strategy based on experimentally designed sampling uses sampling scores, which is similar to the leverage scores used in the matrix approximation. We show that while both strategies are unbiased estimators for the low-frequency components, the convergence rate of experimentally designed sampling is much faster than that of random sampling when a graph is irregular1. We validate the proposed recovery strategies on three specific graphs: a ring graph, an Erdös-Rényi graph, and a star graph. The simulation results support the theoretical analysis.

5. Discrete Signal Processing on Graphs: Sampling Theory Chen, S., Varma, R., Sandryhaila, A., and Kovačević, J. IEEE Transactions on Signal Processing 2015 [Abs]

   We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erdös-Rényi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.

talks