 Award ID(s):
 1736448
 NSFPAR ID:
 10078994
 Date Published:
 Journal Name:
 57th IEEE Conference on Decision and Control (CDC)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Classical results in sparse recovery guarantee the exact reconstruction of ssparse signals under assumptions on the dictionary that are either too strong or NPhard to check. Moreover, such results may be pessimistic in practice since they are based on a worstcase analysis. In this paper, we consider the sparse recovery of signals defined over a graph, for which the dictionary takes the form of an incidence matrix. We derive necessary and sufficient conditions for sparse recovery, which depend on properties of the cycles of the graph that can be checked in polynomial time. We also derive supportdependent conditions for sparse recovery that depend only on the intersection of the cycles of the graph with the support of the signal. Finally, we exploit sparsity properties on the measurements and the structure of incidence matrices to propose a specialized subgraphbased recovery algorithm that outperforms the standard l1 minimization approach.more » « less

null (Ed.)Abstract One of the classical approaches for estimating the frequencies and damping factors in a spectrally sparse signal is the MUltiple SIgnal Classification (MUSIC) algorithm, which exploits the lowrank structure of an autocorrelation matrix. Lowrank matrices have also received considerable attention recently in the context of optimization algorithms with partial observations, and nuclear norm minimization (NNM) has been widely used as a popular heuristic of rank minimization for lowrank matrix recovery problems. On the other hand, it has been shown that NNM can be viewed as a special case of atomic norm minimization (ANM), which has achieved great success in solving line spectrum estimation problems. However, as far as we know, the general ANM (not NNM) considered in many existing works can only handle frequency estimation in undamped sinusoids. In this work, we aim to fill this gap and deal with damped spectrally sparse signal recovery problems. In particular, inspired by the dual analysis used in ANM, we offer a novel optimizationbased perspective on the classical MUSIC algorithm and propose an algorithm for spectral estimation that involves searching for the peaks of the dual polynomial corresponding to a certain NNM problem, and we show that this algorithm is in fact equivalent to MUSIC itself. Building on this connection, we also extend the classical MUSIC algorithm to the missing data case. We provide exact recovery guarantees for our proposed algorithms and quantify how the sample complexity depends on the true spectral parameters. In particular, we provide a parameterspecific recovery bound for lowrank matrix recovery of jointly sparse signals rather than use certain incoherence properties as in existing literature. Simulation results also indicate that the proposed algorithms significantly outperform some relevant existing methods (e.g., ANM) in frequency estimation of damped exponentials.more » « less

Sparse coding, which refers to modeling a signal as sparse linear combinations of the elements of a learned dictionary, has proven to be a successful (and interpretable) approach in applications such as signal processing, computer vision, and medical imaging. While this success has spurred much work on provable guarantees for dictionary recovery when the learned dictionary is the same size as the groundtruth dictionary, work on the setting where the learned dictionary is larger (or overrealized) with respect to the ground truth is comparatively nascent. Existing theoretical results in this setting have been constrained to the case of noiseless data. We show in this work that, in the presence of noise, minimizing the standard dictionary learning objective can fail to recover the elements of the groundtruth dictionary in the overrealized regime, regardless of the magnitude of the signal in the datagenerating process. Furthermore, drawing from the growing body of work on selfsupervised learning, we propose a novel masking objective for which recovering the groundtruth dictionary is in fact optimal as the signal increases for a large class of datagenerating processes. We corroborate our theoretical results with experiments across several parameter regimes showing that our proposed objective also enjoys better empirical performance than the standard reconstruction objective.more » « less

Inferring graph structure from observations on the nodes is an important and popular network science task. Departing from the more common inference of a single graph, we study the problem of jointly inferring multiple graphs from the observation of signals at their nodes (graph signals), which are assumed to be stationary in the sought graphs. Graph stationarity implies that the mapping between the covariance of the signals and the sparse matrix representing the underlying graph is given by a matrix polynomial. A prominent example is that of Markov random fields, where the inverse of the covariance yields the sparse matrix of interest. From a modeling perspective, stationary graph signals can be used to model linear network processes evolving on a set of (not necessarily known) networks. Leveraging that matrix polynomials commute, a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs are provided when perfect covariance information is available. Particularly important from an empirical viewpoint, we provide highprobability bounds on the recovery error as a function of the number of signals observed and other key problem parameters. Numerical experiments demonstrate the effectiveness of the proposed method with perfect covariance information as well as its robustness in the noisy regime.more » « less

Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$colors using a simple greedy algorithm. Remarkably, recent work has shown thatone can find such a coloring even in the semistreaming model. But, in reality,one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed,the celebrated \Brooks' theorem states that every (connected) graph besidecliques and odd cycles can be colored with $\Delta$ colors. Can we find a$\Delta$coloring in the semistreaming model as well? We settle this key question in the affirmative by designing a randomizedsemistreaming algorithm that given any graph, with high probability, eithercorrectly declares that the graph is not $\Delta$colorable or outputs a$\Delta$coloring of the graph. The proof of this result starts with a detour. We first (provably) identifythe extent to which the previous approaches for streaming coloring fail for$\Delta$coloring: for instance, all these approaches can handle streams withrepeated edges and they can run in $o(n^2)$ time  we prove that neither ofthese tasks is possible for $\Delta$coloring. These impossibility resultshowever pinpoint exactly what is missing from prior approaches when it comes to$\Delta$coloring. We then build on these insights to design a semistreaming algorithm thatuses $(i)$ a novel sparserecovery approach based on sparsedensedecompositions to (partially) recover the problematic subgraphs of the input the ones that form the basis of our impossibility results  and $(ii)$ anew coloring approach for these subgraphs that allows for recoloring of othervertices in a controlled way without relying on local explorations or findingaugmenting paths that are generally impossible for semistreaming algorithms.We believe both these techniques can be of independent interest.