A Tikhonov-based projection iteration for nonlinear Ill-posed problems with sparsity constraints

In this paper, we consider nonlinear inverse problems where the solution is assumed to have a sparse expansion with respect to a preassigned basis or frame. We develop a scheme which allows to minimize a Tikhonov functional where the usual quadratic regularization term is replaced by a one-homogeneous (typically weighted ℓ _p ) penalty on the coefficients (or isometrically transformed coefficients) of such expansions. For (p < 2), the regularized solution will have a sparser expansion with respect to the basis or frame under consideration. The computation of the regularized solution amounts in our setting to a Landweber-fixed-point iteration with a projection applied in each fixed-point iteration step. The performance of the resulting numerical scheme is demonstrated by solving the nonlinear inverse single photon emission computerized tomography (SPECT) problem.     

Classification and geometric aspects of vector valued Fourier transforms

It is shown that for any locally compact abelian group ?? and 1 ≤ p ≤ 2, the Fourier type p norm with respect to ?? of a bounded linear operator T between Banach spaces, denoted by ‖T |???^??_p‖, satisfies ‖T |???^??_p‖ ≤ ‖T |???^??_p‖, where ?? is the direct product of ?₂, ?₃, ?₄, … It is also shown that if ?? is not of bounded order then Cⁿ_p ‖T |???^??_p‖ ≤ ‖T |???^??_p‖, where ?? is the circle group, n is a onnegative integer and C^p = . From these inequalities, for any locally compact abelian group ?? ‖T |???^??₂‖ ≤ ‖T |???^??₂‖, and moreover if ?? is not of bounded order then ‖T |???^??₂‖ = ‖T |???^??₂‖. The Hilbertian property and B‐convexity are discussed in the framework of Fourier type p norms. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

For most large underdetermined systems of equations,the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

We consider inexact linear equations y ≈ Φx where y is a given vector in ?ⁿ, Φ is a given n × m matrix, and we wish to find x_0,? as sparse as possible while obeying ‖y ? Φx_0,?‖₂ ≤ ?. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the ??₁‐minimization problem is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x_0,? is sufficiently sparse, then the solution x_1,? of the ??₁‐minimization problem is a good approximation to x_0,?. We suppose that the columns of Φ are normalized to the unit ??₂‐norm, and we place uniform measure on such Φ. We study the underdetermined case where m ～ τn and τ > 1, and prove the existence of ρ = ρ(τ) > 0 and C = C(ρ, τ) so that for large n and for all Φ's except a negligible fraction, the following approximate sparse solution property of Φ holds: for every y having an approximation ‖y ? Φx₀‖₂ ≤ ? by a coefficient vector x₀ ∈ ?^m with fewer than ρ · n nonzeros, This has two implications. First, for most Φ, whenever the combinatorial optimization result x_0,? would be very sparse, x_1,? is a good approximation to x_0,?. Second, suppose we are given noisy data obeying y = Φx₀ + z where the unknown x₀ is known to be sparse and the noise ‖z‖₂ ≤ ?. For most Φ, noise‐tolerant ??₁‐minimization will stably recover x₀ from y in the presence of noise z. We also study the barely determined case m = n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost‐spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. © 2006 Wiley Periodicals, Inc.     

The steady states and convergence to equilibria for a 1‐D chemotaxis model with volume‐filling effect

We consider a chemotaxis model with volume‐filling effect introduced by Hillen and Painter. They also proved the existence of global solutions for a compact Riemannian manifold without boundary. Moreover, the existence of a global attractor in W^{1, p}(Ω??ⁿ), p>n, p?2, was proved by Wrzosek. He also proved that the ω‐limit set consists of regular stationary solutions. In this paper, we prove that the 1‐D stationary problem has at most an infinitely countable number of regular solutions. Furthermore, we show that as t→∞ the solution of the 1‐D evolution problem converges to an equilibrium in W^{1, p}, p?2. Copyright © 2009 John Wiley & Sons, Ltd.     

Rapid error reduction for block Gauss–Seidel based on p‐hierarchical basis

We consider a two‐level block Gauss–Seidel iteration for solving systems arising from finite element discretizations employing higher‐order elements. A p‐hierarchical basis is used to induce this block structure. Using superconvergence results normally employed in the analysis of gradient recovery schemes, we argue that a massive reduction of the H¹‐error occurs in the first iterate, so that the discrete solution is adequately resolved in very few iterates—sometimes a single iteration is sufficient. Numerical experiments on uniform and adapted meshes support these claims. Copyright © 2012 John Wiley & Sons, Ltd.     

Iterated hard-thresholding for linear inverse problems with sparsity constraints

We describe an iterative algorithm for the minimization of Tikhonov type functionals which involve sparsity constraints in form of ℓ^p -penalties which have been proposed recently for the regularization of ill-posed problems. In contrast to the well-known algorithm considered by Daubechies, Defrise and De Mol, it uses hard instead of soft thresholding. This hard thresholding algorithm is based on the generalized conditional gradient method. General results on the convergence of the generalized conditional gradient method enable us to prove strong convergence of the iterates. Furthermore we are able to establish convergence rates of O (n^–1/2) and O (λⁿ) for p = 1 and 1 < p ≤ 2 respectively. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lp error estimates and superconvergence for covolume or finite volume element methods

We consider convergence of the covolume or finite volume element solution to linear elliptic and parabolic problems. Error estimates and superconvergence results in the L^p norm, 2 ≤ p ≤ ∞, are derived. We also show second‐order convergence in the L^p norm between the covolume and the corresponding finite element solutions and between their gradients. The main tools used in this article are an extension of the “supercloseness” results in Chou and Li [Math Comp 69(229) (2000), 103–120] to the L^p based spaces, duality arguments, and the discrete Green's function method. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 463–486, 2003     

Bernstein–Nikolskii and Plancherel–Polya inequalities in Lp ‐norms on non‐compact symmetric spaces

By using Bernstein‐type inequality we define analogs of spaces of entire functions of exponential type in L_p (X), 1 ≤ p ≤ ∞, where X is a symmetric space of non‐compact. We give estimates of L_p ‐norms, 1 ≤ p ≤ ∞, of such functions (the Nikolskii‐type inequalities) and also prove the L_p ‐Plancherel–Polya inequalities which imply that our functions of exponential type are uniquely determined by their inner products with certain countable sets of measures with compact supports and can be reconstructed from such sets of “measurements” in a stable way (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Error estimates for finite volume element methods for general second‐order elliptic problems

We treat the finite volume element method (FVE) for solving general second order elliptic problems as a perturbation of the linear finite element method (FEM), and obtain the optimal H¹ error estimate, H¹ superconvergence and L^p (1 < p ≤ ∞) error estimates between the solution of the FVE and that of the FEM. In particular, the superconvergence result does not require any extra assumptions on the mesh except quasi‐uniform. Thus the error estimates of the FVE can be derived by the standard error estimates of the FEM. Moreover we consider the effects of numerical integration and prove that the use of barycenter quadrature rule does not decrease the convergence orders of the FVE. The results of this article reveal that the FVE is in close relationship with the FEM. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 693–708, 2003.     

MAX k‐CUT and approximating the chromatic number of random graphs

We consider the MAX k‐CUT problem on random graphs G_n,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)^‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of G_n,p, 1/n ≤ p ≤ 0.99, within a factor of O((np)^1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002     

Discrete duality finite volume schemes for Leray−Lions−type elliptic problems on general 2D meshes

Discrete duality finite volume schemes on general meshes, introduced by Hermeline and Domelevo and Omnès for the Laplace equation, are proposed for nonlinear diffusion problems in 2D with nonhomogeneous Dirichlet boundary condition. This approach allows the discretization of non linear fluxes in such a way that the discrete operator inherits the key properties of the continuous one. Furthermore, it is well adapted to very general meshes including the case of nonconformal locally refined meshes. We show that the approximate solution exists and is unique, which is not obvious since the scheme is nonlinear. We prove that, for general W^?1,p′(Ω) source term and W^1‐(1/p),p(?Ω) boundary data, the approximate solution and its discrete gradient converge strongly towards the exact solution and its gradient, respectively, in appropriate Lebesgue spaces. Finally, error estimates are given in the case where the solution is assumed to be in W^2,p(Ω). Numerical examples are given, including those on locally refined meshes. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

A note on the complexity of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> minimization

We discuss the L _p (0 ≤ p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.     

New models for locating a moving service facility

In this paper we analyze a new location problem which is a generalization of the well-known single facility location model. This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single facility location problem on L ^p spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial step function belong to a subspace of L ^p called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm does not have to converge to an optimal solution of the considered problem while the proposed algorithm does.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

In this article, we present a fast and stable algorithm for solving a class of optimization problems that arise in many statistical estimation procedures, such as sparse fused lasso over a graph, convex clustering, and trend filtering, among others. We propose a so-called augmented alternating direction methods of multipliers (ADMM) algorithm to solve this class of problems. Compared to a standard ADMM algorithm, our proposal significantly reduces the computational cost at each iteration while maintaining roughly the same overall convergence speed. We also consider a new varying penalty scheme for the ADMM algorithm, which could further accelerate the convergence, especially when solving a sequence of problems with tuning parameters of different scales. Extensive numerical experiments on the sparse fused lasso problem show that the proposed algorithm is more efficient than the standard ADMM and two other existing state-of-the-art specialized algorithms. Finally, we discuss a possible extension and some interesting connections to two well-known algorithms. Supplementary materials for the article are available online.     

Products of operator ideals and extensions of Schatten classes

We study relations between Schatten classes and product operator ideals, where one of the factors is the Banach ideal Π_E,2 of (E, 2)‐summing operators, and where E is a Banach sequence space with ?₂ ? E. We show that for a large class of 2‐convex symmetric Banach sequence spaces the product ideal Π_E,2 ○ ??^a_q,s is an extension of the Schatten class ??_F with a suitable Lorentz space F. As an application, we obtain that if 2 ≤ p, q < ∞, 1/r = 1/p + 1/q and E is a 2‐convex symmetric space with fundamental function λ_E(n) ≈? n^1/p, then Π_E,2 ○ Π_q is an extension of the Schatten class ??r,q (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stepanov‐like doubly weighted pseudo almost automorphic processes and its application to Sobolev‐type stochastic differential equations driven by G‐Brownian motion

This paper investigates the properties of the p‐mean Stepanov‐like doubly weighted pseudo almost automorphic (S^pDWPAA) processes and its application to Sobolev‐type stochastic differential equations driven by G‐Brownian motion. We firstly prove the equivalent relation between the S^pDWPAA and Stepanov‐like asymptotically almost automorphic stochastic processes based on ergodic zero set. We further establish the completeness of the space and the composition theorem for S^pDWPAA processes. These results obtained improve and extend previous related conclusions. As an application, we show the existence and uniqueness of the S^p DWPAA solution for a class of nonlinear Sobolev‐type stochastic differential equations driven by G‐Brownian motion and present a decomposition of this unique solution. Moreover, an example is given to illustrate the effectiveness of our results.     

Localized nonlinear functional equations and two sampling problems in signal processing

Let 1 ≤ p ≤ ∞. In this paper, we consider solving a nonlinear functional equation f (x) = y, where x, y belong to ? ^p and f has continuous bounded gradient in an inverse-closed subalgebra of ? (?²), the Banach algebra of all bounded linear operators on the Hilbert space ? ². We introduce strict monotonicity property for functions f on Banach spaces ? ^p so that the above nonlinear functional equation is solvable and the solution x depends continuously on the given data y in ? ^p . We show that the Van-Cittert iteration converges in ? ^p with exponential rate and hence it could be used to locate the true solution of the above nonlinear functional equation. We apply the above theory to handle two problems in signal processing: nonlinear sampling termed with instantaneous companding and subsequently average sampling; and local identification of innovation positions and qualification of amplitudes of signals with finite rate of innovation.