Structured sparse optimization is an important and challenging problem for analyzing high-dimensional data in a variety of applications such as bioinformatics, medical imaging, social networks, and astronomy. Although a number of structured sparsity models have been explored, such as trees, groups, clusters, and paths, connected subgraphs have been rarely explored in the current literature. One of the main technical challenges is that there is no structured sparsity-inducing norm that can directly model the space of connected subgraphs, and there is no exact implementation of a projection oracle for connected subgraphs due to its NP-hardness. In this paper, we explore efficient approximate projection oracles for connected subgraphs, and propose two new efficient algorithms, namely, Graph-IHT and Graph-GHTP, to optimize a generic nonlinear objective function subject to connectivity constraint on the support of the variables. Our proposed algorithms enjoy strong guarantees analogous to several current methods for sparsity-constrained optimization, such as Projected Gradient Descent (PGD), Approximate Model Iterative Hard Thresholding (AM-IHT), and Gradient Hard Thresholding Pursuit (GHTP) with respect to convergence rate and approximation accuracy. We apply our proposed algorithms to optimize several well-known graph scan statistics in several applications of connected subgraph detection as a case study, and the experimental results demonstrate that our proposed algorithms outperform state-of-the-art methods.
The methods in this category have been briefly reviewed in the introduction section. The most relevant work is by @cite_6 . The authors present -, a variant of @cite_14 , for compressive sensing and linear regression problems based on head and tail approximations of @math .
@cite_14 @cite_6
2592715613 2022240529 2067878805 2163973643
Two compressive sensing inspired approaches for the solution of non-linear inverse scattering problems are introduced and discussed. Differently from the sparsity promoting approaches proposed in most of the papers published in the literature, the two methods here tackle the problem in its full non-linearity, by adopting a contrast source inversion scheme. In the first approach, the @math -norm of the unknown is added as a weighted penalty term to the contrast source cost functional. The second, and (to the best of our knowledge) completely original, approach enforces sparsity by constraining the solution of the non-linear problem into a convex set defined by the @math -norm of the unknown. A numerical assessment against a widely used benchmark example (the “Austria” profile) is given to assess the capabilities of the proposed approaches. Notably, the two approaches can be applied to any kind of basis functions and they can successfully tackle both reduced number of data (with respect to Nyquist sampling) and or overcomplete dictionaries. The theory of compressive sensing (CS) has shown us that under certain conditions, a sparse signal can be recovered from a small number of linear incoherent measurements. An effective class of reconstruction algorithms involve solving a convex optimization program that balances the l1 norm of the solution against a data fidelity term. Tremendous progress has been made in recent years on algorithms for solving these l1 minimization programs. These algorithms, however, are for the most part static: they focus on finding the solution for a fixed set of measurements. In this paper, we present a suite of dynamic algorithms for solving l1 minimization programs for streaming sets of measurements. We consider cases where the underlying signal changes slightly between measurements, and where new measurements of a fixed signal are sequentially added to the system. We develop algorithms to quickly update the solution of several different types of l1 optimization problems whenever these changes occur, thus avoiding having to solve a new optimization problem from scratch. Our proposed schemes are based on homotopy continuation, which breaks down the solution update in a systematic and efficient way into a small number of linear steps. Each step consists of a low-rank update and a small number of matrix-vector multiplications - very much like recursive least squares. Our investigation also includes dynamic updating schemes for l1 decoding problems, where an arbitrary signal is to be recovered from redundant coded measurements which have been corrupted by sparse errors. Compressive Sensing theory details how a sparsely represented signal in a known basis can be reconstructed with an underdetermined linear measurement model. However, in reality there is a mismatch between the assumed and the actual bases due to factors such as discretization of the parameter space defining basis components, sampling jitter in A D conversion, and model errors. Due to this mismatch, a signal may not be sparse in the assumed basis, which causes significant performance degradation in sparse reconstruction algorithms. To eliminate the mismatch problem, this paper presents a novel perturbed orthogonal matching pursuit (POMP) algorithm that performs controlled perturbation of selected support vectors to decrease the orthogonal residual at each iteration. Based on detailed mathematical analysis, conditions for successful reconstruction are derived. Simulations show that robust results with much smaller reconstruction errors in the case of perturbed bases can be obtained as compared to standard sparse reconstruction techniques. Recent compressive sensing results show that it is possible to accurately reconstruct certain compressible signals from relatively few linear measurements via solving nonsmooth convex optimization problems. In this paper, we propose the use of the alternating direction method - a classic approach for optimization problems with separable variables (D. Gabay and B. Mercier, ?A dual algorithm for the solution of nonlinear variational problems via finite-element approximations,? Computer and Mathematics with Applications, vol. 2, pp. 17-40, 1976; R. Glowinski and A. Marrocco, ?Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires,? Rev. Francaise dAut. Inf. Rech. Oper., vol. R-2, pp. 41-76, 1975) - for signal reconstruction from partial Fourier (i.e., incomplete frequency) measurements. Signals are reconstructed as minimizers of the sum of three terms corresponding to total variation, ?1-norm of a certain transform, and least squares data fitting. Our algorithm, called RecPF and published online, runs very fast (typically in a few seconds on a laptop) because it requires a small number of iterations, each involving simple shrinkages and two fast Fourier transforms (or alternatively discrete cosine transforms when measurements are in the corresponding domain). RecPF was compared with two state-of-the-art algorithms on recovering magnetic resonance images, and the results show that it is highly efficient, stable, and robust.