Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization

• URL: http://arxiv.org/abs/2509.14836v1
• Date: Thu, 18 Sep 2025 10:57:52 GMT
• Title: Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization
• Abstract summary: This paper includes a method for a broad class of graph signals, designed to attain the best possible recovery based on the general theory.<n>An existing method for flexible sampling is able to control the number of active vertices for sampling, mandatory inclusion or exclusion.<n>The effectiveness is demonstrated through experiments on various graph signal models.
• Score: 22.188214983252507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a method for vertex-wise flexible sampling of a broad class of graph signals, designed to attain the best possible recovery based on the generalized sampling theory. This is achieved by designing a sampling operator by an optimization problem, which is inherently non-convex, as the best possible recovery imposes a rank constraint. An existing method for vertex-wise flexible sampling is able to control the number of active vertices but cannot incorporate prior knowledge of mandatory or forbidden vertices. To address these challenges, we formulate the operator design as a problem that handles a constraint of the number of active vertices and prior knowledge on specific vertices for sampling, mandatory inclusion or exclusion. We transformed this constrained problem into a difference-of-convex (DC) optimization problem by using the nuclear norm and a DC penalty for vertex selection. To solve this, we develop a convergent solver based on the general double-proximal gradient DC algorithm. The effectiveness of our method is demonstrated through experiments on various graph signal models, including real-world data, showing superior performance in the recovery accuracy by comparing to existing methods.

Related papers

• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• Solving Inverse Problems via Diffusion Optimal Control [3.0079490585515343]
  We derive a diffusion-based optimal controller inspired by the iterative Linear Quadratic Regulator (iLQR) algorithm.<n>We show that the idealized posterior sampling equation can be recovered as a special case of our algorithm.<n>We then evaluate our method against a selection of neural inverse problem solvers, and establish a new baseline in image reconstruction with inverse problems.
  arXiv  Detail & Related papers  (2024-12-21T19:47:06Z)
• The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models [75.33431791218302]
  Deep Neural Network Network (DNN) models are used for programming purposes. In this paper we examine the use of convex neural recovery models. We show that all the stationary non-dimensional objective objective can be characterized as the standard a global subsampled convex solvers program. We also show that all the stationary non-dimensional objective objective can be characterized as the standard a global subsampled convex solvers program.
  arXiv  Detail & Related papers  (2023-12-19T23:04:56Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• A Combinatorial Perspective on the Optimization of Shallow ReLU Networks [35.329916555349214]
  NP-hard problem of optimizing a shallow ReLU network can be characterized as a search over each training example's activation pattern. We show that it can be naturally modeled via a zonotope with its set is to the set of feasible activation patterns.
  arXiv  Detail & Related papers  (2022-10-01T03:09:02Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results [6.355764634492975]
  We introduce a convex relaxation for quadratically-constrained quadratic programs, along with a penalized parabolic relaxation to near near feasible solutions. We show that starting from a sequential point-to-point solution satisfying certain conditions, the penalized parabolic relaxation convergences satisfies certain conditions Karush-Kuhn optimal regularity problem.
  arXiv  Detail & Related papers  (2022-08-07T02:58:04Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Sparse Signal Reconstruction for Nonlinear Models via Piecewise Rational Optimization [27.080837460030583]
  We propose a method to reconstruct degraded signals by a nonlinear distortion and at a limited sampling rate. Our method formulates as a non exact fitting term and a penalization term. It is shown how to use the problem in terms of the benefits of our simulations.
  arXiv  Detail & Related papers  (2020-10-29T09:05:19Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  We present a new model of a general convex or non objective machine machine objectives. We propose an algorithm that solves a constraint with gradually relaxed point levels of each subproblem. We demonstrate the effectiveness of our new numerical scale problems.
  arXiv  Detail & Related papers  (2020-10-23T05:24:05Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.