We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a cor…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “graph signal recovery”
This work aims at recovering signals that are sparse on graphs. Compressed sensing offers techniques for signal recovery from a few linear measurements and graph Fourier analysis provides a signal representation on graph. In this paper, we leverage these two frameworks to introduce a new Lasso recovery algorithm on gra…
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, which generalizes the bandlimited class and is similar to the globally smooth class. We then propose two recovery s…
LogSpecT learns graphs from stationary signals without infeasibility issues.
problem Infeasibility of SpecT model for graph learning from stationary signals.
method Design of LogSpecT and rLogSpecT models with recovery guarantees.
result rLogSpecT is always feasible and provides recovery guarantees.
The paper infers multiple graphs from stationary signals on them.
problem Inferring multiple graphs from signals observed on their nodes.
method Convex optimization method leveraging matrix polynomial commutation.
result High-probability bounds on recovery error provided.
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 exhibi…
It has been shown recently that graph signals with small total variation can be accurately recovered from only few samples if the sampling set satisfies a certain condition, referred to as the network nullspace property. Based on this recovery condition, we propose a sampling strategy for smooth graph signals based on …
We consider estimating a piecewise-constant image, or a gradient-sparse signal on a general graph, from noisy linear measurements. We propose and study an iterative algorithm to minimize a penalized least-squares objective, with a penalty given by the "l_0-norm" of the signal's discrete graph gradient. The method proce…
Unified framework infers time-varying graphs from incomplete signals.
problem Jointly inferring time-varying network topologies and imputing missing data from partial observations.
method Unified non-convex optimization framework with Proximal Alternating Direction Method of Multipliers (PADMM) algorithm.
result Superior robustness in high missing-data regimes, demonstrated through extensive numerical experiments.
Graph signals offer a very generic and natural representation for data that lives on networks or irregular structures. The actual data structure is however often unknown a priori but can sometimes be estimated from the knowledge of the application domain. If this is not possible, the data structure has to be inferred f…
Proposes an offline active learning method for graphs.
problem Active learning on graphs where labeling is expensive.
method Two-stage biased sampling strategy considering informativeness and representativeness.
result Establishes a theoretical relationship between generalization error and number of nodes selected.
New method recovers graph latent positions under edge differential privacy.
problem Recovering latent graph information from privatized graphs.
method Applying geometric insights to adjust statistical inference for privatized graphs.
result Achieves consistent recovery of latent positions under local edge differential privacy constraints.
Proposes a new graph trend filtering model for inhomogeneous graph signals.
problem Estimating piecewise smooth signals over a graph with varying smoothness levels.
method Introduces a l2,0 norm penalized Graph Trend Filtering (GTF) model and two solution methods: spectral decomposition and simulated annealing.
result The GTF model performs better than existing approaches in denoising, support recovery, and semi-supervised classification.
This paper considers regression tasks involving high-dimensional multivariate processes whose structure is dependent on some {known} graph topology. We put forth a new definition of time-vertex wide-sense stationarity, or joint stationarity for short, that goes beyond product graphs. Joint stationarity helps by reducin…
Study on signal recovery from low-rank matrix with sparse noise.
problem Inference of a rank-one signal in the presence of sparse noise.
method Replica method from statistical physics, recursive distributional equations, population dynamics algorithm.
result Critical signal strength for recovery via top eigenvector identified.
We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the co…
We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, …
Paper recovers lattice signal partitions efficiently.
problem Estimating lattice partition from noisy data.
method Uses dyadic CART for computationally-efficient partition recovery.
result Consistently estimates partition with optimal error rate.
This paper improves support recovery in universal one-bit compressed sensing.
problem Support recovery in one-bit compressed sensing for sparse signals.
method Proposes approximate support recovery and superset recovery algorithms with polynomial-time complexity.
result Achieves improved support recovery with fewer measurements compared to existing methods.
Paper proposes efficient methods for clustering and signal recovery in high-dimensional data with block structures.
problem High-dimensional clustering and signal recovery under block signal structures.
method CFA-PCA and MA-PCA methods for sparse and dense block signals.
result Proposed methods achieve computational minimax optimality for clustering and signal recovery.
Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
We present a novel condition, which we term the net- work nullspace property, which ensures accurate recovery of graph signals representing massive network-structured datasets from few signal values. The network nullspace property couples the cluster structure of the underlying network-structure with the geometry of th…
Active graph-based semi-supervised learning (AG-SSL) aims to select a small set of labeled examples and utilize their graph-based relation to other unlabeled examples to aid in machine learning tasks. It is also closely related to the sampling theory in graph signal processing. In this paper, we revisit the original fo…
We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corrup…
We discuss a variant of `blind' community detection, in which we aim to partition an unobserved network from the observation of a (dynamical) graph signal defined on the network. We consider a scenario where our observed graph signals are obtained by filtering white noise input, and the underlying network is different …
Study on detecting and recovering hidden dense cycles in random graphs.
problem Detecting and recovering hidden dense cycles in random graphs.
method Information-theoretic analysis of thresholds for detection and recovery.
result Characterization of information-theoretic thresholds for detection and recovery.
A new method enhances signal recovery with FDR control.
problem Challenging signal recovery in compressive sensing.
method Knockoff-guided compressive sensing framework with FDR control.
result Guaranteed FDR control leads to more accurate signal reconstruction.
This paper improves support recovery in universal one-bit compressed sensing with fewer measurements.
problem Support recovery in universal one-bit compressed sensing.
method Developed algorithms to recover the support of sparse signals with a small number of false positives.
result Support recovery with measurements, improving to with known dynamic range.
We discuss a general notion of "sparsity structure" and associated recoveries of a sparse signal from its linear image of reduced dimension possibly corrupted with noise. Our approach allows for unified treatment of (a) the "usual sparsity" and "usual recovery," (b) block-sparsity with possibly overlapping blo…
Signal recovery is one of the key techniques of Compressive sensing (CS). It reconstructs the original signal from the linear sub-Nyquist measurements. Classical methods exploit the sparsity in one domain to formulate the L0 norm optimization. Recent investigation shows that some signals are sparse in multiple domains.…
The paper optimizes sensor selection for network time series data.
problem Optimizing sensor selection for network time series data with minimal error.
method Data-driven strategies to turn off sensors or select a sampling set of nodes.
result Proposes and compares various data-driven strategies for sensor selection.
SMM improves signal recovery from noisy data.
problem Estimating signals from noisy and scaled observations.
method Spiked mixture model (SMM) with EM algorithm.
result SMM outperforms GMM in signal recovery.
Paper discusses new stochastic algorithms for sparse signal recovery.
problem Sparse signal recovery in medical imaging and remote sensing.
method Proposes and analyzes stochastic natural thresholding algorithms.
result Demonstrates improved performance of StoNT algorithms.
Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high dimensional ambient space. We introduce SPIN, a first order projected gradient method to recover the signal components. Despite the…
New method recovers signals from compressed measurements using generative networks with contractive layers.
problem Signal recovery from compressed measurements with generative network priors.
method Developed a new matrix concentration inequality (R2WDC) to relax expansivity conditions for generative networks.
result Signals in the range of a Gaussian generative network can be recovered from few linear measurements with contractive layers.
In this paper, we consider the block-sparse signals recovery problem in the context of multiple measurement vectors (MMV) with common row sparsity patterns. We develop a new method for recovery of common row sparsity MMV signals, where a pattern-coupled hierarchical Gaussian prior model is introduced to characterize bo…
In this paper we develop a novel computational sensing framework for sensing and recovering structured signals. When trained on a set of representative signals, our framework learns to take undersampled measurements and recover signals from them using a deep convolutional neural network. In other words, it learns a tra…
This letter presents a novel Block Bayesian Hypothesis Testing Algorithm (Block-BHTA) for reconstructing block sparse signals with unknown block structures. The Block-BHTA comprises the detection and recovery of the supports, and the estimation of the amplitudes of the block sparse signal. The support detection and rec…
New method for identifying graph shift operators using vertex-time autoregressive models.
problem Identifying graph shift operators from graph signals.
method Online optimization using vertex-time autoregressive model and stochastic gradient projection.
result Successful recovery of graph shift operators from graph signals.
Matching Pursuit LASSIn Part I \cite{TanPMLPart1}, a Matching Pursuit LASSO ({MPL}) algorithm has been presented for solving large-scale sparse recovery (SR) problems. In this paper, we present a subspace search to further improve the performance of MPL, and then continue to address another major challenge of SR -- bat…
How Does Attention Help? Insights from Random Matrices on Signal Recovery from Sequence Modelsstat.ML
Study reveals how attention helps in signal recovery from sequence models using random matrix theory.
problem Signal recovery from sequence models with attention mechanisms.
method Analysis of sample covariance matrices constructed from pooled sequence representations with attention weights.
result Optimal attention weights maximize signal-to-noise ratio and improve signal recovery.
Efficiently recovers network community structure from clients' small subgraphs.
problem Recovering community structure in federated myopic learning settings.
method Developed an algorithm to compute consensus signed weighted graph from clients' evidence.
result Exact recovery of network structure is possible in polynomial time under certain conditions.
This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse v…
Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysiscs.LG
The paper tackles subspace-preserving recovery of sparse signals from overcomplete dictionaries.
problem Recovering sparse signals from overcomplete dictionaries when the signal lies in a subspace of the dictionary.
method Geometric conditions and covering radius/angular distance to ensure subspace-preserving recovery.
result Theoretical analysis shows that subspace-preserving recovery is possible without requiring incoherence or restricted isometry of the dictionary.
The promise of compressive sensing (CS) has been offset by two significant challenges. First, real-world data is not exactly sparse in a fixed basis. Second, current high-performance recovery algorithms are slow to converge, which limits CS to either non-real-time applications or scenarios where massive back-end comput…
This work uses diffusion models for accurate signal recovery from semi-parametric models.
problem Recovering signals from semi-parametric single index models with discontinuous link functions.
method Proposes an efficient reconstruction method using diffusion models that requires one round of sampling and inversion.
result Demonstrates more accurate reconstructions with fewer evaluations compared to competing methods.
Machine learning, and more specifically deep learning, have shown remarkable performance in sensing, communications, and inference. In this paper, we consider the application of the deep unfolding technique in the problem of signal reconstruction from its one-bit noisy measurements. Namely, we propose a model-based mac…
In this paper, we study the recovery of a signal from a set of noisy linear projections (measurements), when such projections are unlabeled, that is, the correspondence between the measurements and the set of projection vectors (i.e., the rows of the measurement matrix) is not known a priori. We consider a special case…