In this paper, we propose and investigate algorithms for the structured orthogonal dictionary learning problem. First, we investigate the case when the dictionary is a Householder matrix. We give sample complexity results and show theoretically guaranteed approximate recovery (in the l∞sense) with optimal computational complexity. We then attempt to generalize these techniques when the dictionary is a product of a few Householder matrices. We numerically validate these techniques in the sample-limited setting to show performance similar to or better than existing techniques while having much improved computational complexity.

Given partial measurements of a time-varying graph signal, we propose an algorithm to simultaneously estimate both the underlying graph topology and the missing measurements. The proposed algorithm operates by training an interpretable neural network, designed from the unrolling framework. The proposed technique can be used as a graph learning and/or a graph signal reconstruction algorithm. This work builds on prior work in graph learning by tailoring the learned graph to the signal reconstruction task; and also enhances prior work in graph signal reconstruction by allowing the underlying graph to be unknown.

We consider the problem of building numerically stable algorithms for computing Discrete Fourier Transform (DFT) of$N$- length signals with known frequency support of size$k$. A typical algorithm, in this case, would involve solving (possibly poorly conditioned) a system of equations, causing numerical instability. When$N$is a power of 2, and the frequency support is a random subset of$\mathbb{Z}_{N}$, we provide an algorithm that has (a possibly optimal)$O(k\log k)$complexity to compute the DFT while solving system of equations that are$O(1)$in size.

Suppose an$N-$length signal has known frequency support of size$k$. Given access to samples of this signal, how fast can we compute the DFT? The answer to this question depends on the structure of the frequency support. We first identify some frequency supports for which (an ideal)$O(k \log k)$complexity can be achieved, which we refer to as homogeneous sets. We give a generalization of the radix-2 FFT that enables$O(k\log k)$computation of signals with homogeneous frequency support. We use homogeneous sets as building blocks to construct more complex support structures for which the complexity of$O(k\log k)$is achievable. Applying these ideas, we present an$O(k\log ^{2}k)$algorithm for computing the DFT of signals whose frequency support is additively structured. We also present partial converses.

We present an algorithm for inferring an unknown graph from time-indexed signals corresponding to the graph nodes . The signals are assumed to consist of a few dominant, yet unknown, frequencies within the graph spectrum, consistent across all time points, as well as sparse, potentially temporally incoherent corruptions. These corruptions may serve as relevant features for classification in neurological applications. We apply our algorithm to neuropsychiatric datasets, including ADHD , OPEN-NEURO , and COBRE , in order to learn graphs for patients and controls. The learned graphs, used as features for classification, result in higher classification accuracy compared to existing graph learning methods. Furthermore, our proposed model generates more connected or “small-world” networks, consistent with previous findings on brain networks . We also demonstrate that the proposed model achieves a better separation between patient and control classes.

The localization of acoustic sources is a parameter estimation problem where the parameters of interest are the direction of arrivals (DOAs). The DOA estimation problem can be formulated as a sparse parameter estimation problem and solved using compressive sensing (CS) methods. In this paper, the CS method of sparse Bayesian learning (SBL) is used to find the DOAs. We specifically use multi-frequency SBL leading to a non-convex optimization problem, which is solved using fixed-point iterations. We evaluate SBL along with traditional DOA estimation methods of conventional beamforming (CBF) and multiple signal classification (MUSIC) on various source localization tasks from the open access LOCATA dataset. The comparative study shows that SBL significantly outperforms CBF and MUSIC on all the considered tasks.

Graph inference plays an essential role in machine learning, pattern recognition, and classification. Signal processing based approaches in literature generally assume some variational property of the observed data on the graph. We make a case for inferring graphs on which the observed data has high variation. We propose a new signal processing based inference model and a new learning criterion that allow for wideband frequency variation in the data and derive an algorithm for graph inference. The proposed inference algorithm consists of two steps: 1) learning orthogonal eigenvectors of a graph from the data; 2) recovering the adjacency matrix of the graph topology from the given graph eigenvectors. The first step is solved by an iterative algorithm with a closed-form solution. In the second step, the adjacency matrix is inferred from the eigenvectors by solving a convex optimization problem. Numerical results on synthetic data show the proposed inference algorithm can effectively capture the meaningful graph topology from observed data under the wideband assumption.

We consider the problem of finding the Discrete Fourier Transform (DFT) of$N$-length signals with known frequency support of size$k$. When$N$is a power of 2 and the frequency support is a spectral set, we provide an$O(k\log k)$algorithm to compute the DFT. Our algorithm uses some recent characterizations of spectral sets and is a generalization of the standard radix-2 algorithm.

We consider the problem of recovering N length vectors h that vanish on a given set of indices and satisfy h*h = h. We give some results on the structure of such h when N is a product of two primes, and investigate some bounds and their connections to certain graphs defined on ZN.

We study the problem of finding unitary submatrices of the$N \times N$discrete Fourier transform matrix, in the context of interpolating a discrete bandlimited signal using an orthogonal basis. This problem is related to a diverse set of questions on idempotents on$\mathbb {Z}_{N}$and tiling$\mathbb {Z}_{N}$. In this work, we establish a graph-theoretic approach and connections to the problem of finding maximum cliques. We identify the key properties of these graphs that make the interpolation problem tractable when$N$is a prime power, and we identify the challenges in generalizing to arbitrary$N$. Finally, we investigate some connections between graph properties and the spectral-tile direction of the Fuglede conjecture.

Consider a unitary (up to scaling) submatrix of the Fourier matrix with rows indexed by I and columns indexed by J. From the column index set J we construct a graph G so that the row index set I determines a max-clique. Interpreting G as coming from an association scheme gives certain bounds on the clique number, which has possible applications to Fuglede's conjecture on spectral and tiling sets.

We study the problem of interpolating all values of a discrete signal f of length N when dJ. The sampling pattern for f is specified by an index set I, and is said to be a universal sampling set if samples in the locations I can be used to interpolate signals from BJfor any J. When N is a prime power we give several characterizations of universal sampling sets, some structure theorems for such sets, an algorithm for their construction, and a formula that counts them. There are also natural applications to additive uncertainty principles.

Video streaming performance on wireless networks is choppy. The culprit is the unpredictable wireless medium, whose fluctuations results in fluctuating throughput and bit errors. Current video codecs are not equipped to handle such variations since they exhibit an all or nothing behavior. If the channel is strong and above a threshold, the video stream gets decoded perfectly. If not, typically nothing gets decoded. Thus, there is no graceful degradation with wireless conditions.