My research can be categorized as follows:

1. Random Asynchronous Linear Systems
2. Sparsity and Uncertainty on Graphs
3. Multirate Processing of Graph Signals
4. Off-grid Problem in Compressed Sensing

Random Asynchronous Linear Systems

Linear state-space recursions arise in a large number of different fields ranging from mathematical finance to implementation of digital filters. Such recursions are also used commonly as power methods in numerical linear algebra, which provide useful tools for data analysis. A notable application is the PageRank algorithm used in search engines for ranking web pages. More recently, state-space models are studied also in the analysis of network defined data, where the state vector is considered as a signal on the graph, and the transition matrix is considered as a local graph operator that encapsulates the connectivity structure of the underlying network. Then, a state recursion can be implemented on the graph in a distributed fashion as a data exchange between the neighboring nodes.

In more practical scenarios, nodes on the graph can communicate with each other asynchronously and randomly. That is, a single node may “wake up” at a random time instance, do some local computations on its own, and then send information to its outgoing neighbors.Such random and asynchronous behavior of the nodes can be modeled with the following asynchronous state recursions:

which is very similar to the classical (synchronous) state recursions except the fact that only a random subset of variables are updated at an iteration, and the remaining ones stay unchanged.

Since the dynamical behavior of randomized asynchronous updates is very different from standard state-space models, in this line work we have focused on the convergence and stability behavior of such random asynchronous recursions. In particular we have shown that an unstable system (in the synchronous world) may be stabilized simply by the use of randomized asynchronicity. Moreover, randomized asynchronicity may result in a lower total computational complexity in some applications.

Demonstration of asynchronous and synchronous recursions on the directed cycle graph of size N = 7. When all the nodes “fire” synchronously, the graph signal is shifted circularly. So, the signal repeats itself after every N synchronous updates. When only a random subset of nodes fire asynchronously, duplicate entries are created, and the signal converges (in the mean-squared sense) to a constant signal on the graph eventually with random asynchronous updates.

Related Publications

Sparsity and Uncertainty on Graphs

The uncertainty principle is an essential mathematical concept in science and engineering, and it explains some fundamental limits in different areas ranging from quantum mechanics to harmonic analysis. In classical signal processing, the uncertainty principle states that a signal cannot be arbitrarily localized in time and frequency simultaneously. More generally, uncertainty principles state that a signal cannot have an arbitrarily "short" description in two different bases simultaneously. Due to its fundamental characterization, uncertainty principles have been useful to design signals, pulse shapes, and filters that are maximally localized in one domain for a given spread in the other domain. Furthermore, they lay a foundation for sparse representation theory and compressed sensing.

Since graph signal processing proposes two different bases (i.e., vertex and the graph Fourier domains) to represent graph signals, my research in this context considers the localization properties of graph signals in these two domains. In particular, I have focused on discrete uncertainty principles based on the notion of sparsity. I have shown that the total number of nonzero elements of a graph signal and its representation in the graph Fourier domain (i.e., graph Fourier transform) is lower bounded by a quantity depending on the underlying graph. In the particular case of directed cycle graph (which relates the graph signal processing to classical signal processing), I have also shown that the proposed inequalities reduce to the well-known uncertainty principles in discrete signal processing.

An eigenvector of a cycle graph of size N has at least N/2 nonzero entries, whereas a complete graph has 2-sparse eigenvectors. Thus, signals on a complete graph can be extremely localized in vertex and graph Fourier domains simultaneously.

Related Publications

Multirate Processing of Graph Signals

Multirate systems and filter banks find many applications in signal processing theory and implementations. Due to its significance and applicability to wide range of problems, extensions of classical multirate signal processing ideas to the case of graphs became a popular sub-field in graph signal processing. The first study showed the possibility of extending 2-channel filter banks to bipartite graphs, as their eigenvalue spectrum has a symmetric structure. However, this relation cannot be generalized to M-channel systems on M-partite graphs. As a result, the extension of classical multirate theory to graphs is nontrivial, and such extensions cannot be obtained without certain mathematical restrictions on the graph. For example, even a simple delay chain system does not provide perfect reconstruction (PR) on an arbitrary graph (as apposed to classical filter banks). My research in this context considered the extension of fundamental building blocks of multirate signal processing theory to the case of graphs . I revisited ideas such as noble identities, aliasing, and polyphase decompositions in graph multirate systems. I provided the necessary conditions on the graph such that these ideas remain valid in the graph domain. In particular, I showed that when the underlying graph satisfies a condition called M-block cyclic property, classical multirate theory can be extended to the graphs.

In general, M-block cyclic property is more restrictive than M-partiteness. Nevertheless, a directed cycle graph of size N, CN, (which relates graph signal processing to classical signal processing) can be represented as an M-block cyclic graph under suitable permutation of the vertices.

Related Publications

Off-grid Problem in Compressed Sensing

Prior to my doctoral work at California Institute of Technology, I studied for M.S. degree where my research focused on robust sparse recovery techniques in the presence of a basis mismatch due to the discretization of the underlying continuous parameter space. Another way to tackle this issue is to formulate an atomic norm minimization problem using the continuous dictionary itself. In the case of line spectral estimation, the atomic norm minimization problem can be written as semi-definite programming using tractable representations of nonnegative trigonometric polynomials. As a part of my doctoral work, I have developed an alternative proof for the SDP representation of atomic norm problems. This is a standalone proof that relies only on fundamental results from matrix theory, and it shows that the bounded lemma from system theory literature directly leads to the SDP formulations.

Related Publications