An iterative algorithm for sparse and constrained recovery with applications to divergence-free current reconstructions in magneto-encephalography

We propose an iterative algorithm for the minimization of a ? ₁-norm penalized least squares functional, under additional linear constraints. The algorithm is fully explicit: it uses only matrix multiplications with the three matrices present in the problem (in the linear constraint, in the data misfit part and in the penalty term of the functional). None of the three matrices must be invertible. Convergence is proven in a finite-dimensional setting. We apply the algorithm to a synthetic problem in magneto-encephalography where it is used for the reconstruction of divergence-free current densities subject to a sparsity promoting penalty on the wavelet coefficients of the current densities. We discuss the effects of imposing zero divergence and of imposing joint sparsity (of the vector components of the current density) on the current density reconstruction.     

Estimation in generalized linear models for functional data via penalized likelihood

We analyze in a regression setting the link between a scalar response and a functional predictor by means of a Functional Generalized Linear Model. We first give a theoretical framework and then discuss identifiability of the model. The functional coefficient of the model is estimated via penalized likelihood with spline approximation. The L² rate of convergence of this estimator is given under smoothness assumption on the functional coefficient. Heuristic arguments show how these rates may be improved for some particular frameworks.     

Factoring matrices with a tree-structured sparsity pattern

Let A be a matrix whose sparsity pattern is a tree with maximal degree d_max. We show that if the columns of A are ordered using minimum degree on |A|+|A|^∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(d_maxn) fill, requires only O(d_maxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of |A|^∗|A| are not as efficient as the approaches that we propose in this paper.     

Non-convex sparse regularisation

We study the regularising properties of Tikhonov regularisation on the sequence space ?² with weighted, non-quadratic penalty term acting separately on the coefficients of a given sequence. We derive sufficient conditions for the penalty term that guarantee the well-posedness of the method, and investigate to which extent the same conditions are also necessary. A particular interest of this paper is the application to the solution of operator equations with sparsity constraints. Assuming a linear growth of the penalty term at zero, we prove the sparsity of all regularised solutions. Moreover, we derive a linear convergence rate under the assumptions of even faster growth at zero and a certain injectivity of the operator to be inverted. These results in particular cover non-convex ?p regularisation with 0<p<1.     

Existence and non-existence of solutions for a class of Monge-Ampère equations

We study the boundary value problems for Monge-Ampère equations: detD²u=e−u in Ω⊂Rn, n?1, u_|∂Ω=0. First we prove that any solution on the ball is radially symmetric by the argument of moving plane. Then we show there exists a critical radius such that if the radius of a ball is smaller than this critical value there exists a solution, and vice versa. Using the comparison between domains we can prove that this phenomenon occurs for every domain. Finally we consider an equivalent problem with a parameter detD²u=e−tu in Ω, u_|∂Ω=0, t?0. By using Lyapunov-Schmidt reduction method we get the local structure of the solutions near a degenerate point; by Leray-Schauder degree theory, a priori estimate and bifurcation theory we get the global structure.     

Multiple positive and 2-nodal symmetric solutions of elliptic problems with critical nonlinearity

We consider the problem −Δu+a(x)u=f(x)|u|^2*−2u in Ω, u=0 on ∂Ω, where Ω is a bounded smooth domain in RN, N?4, is the critical Sobolev exponent, and a,f are continuous functions. We assume that Ω, a and f are invariant under the action of a group of orthogonal transformations. We obtain multiplicity results which contain information about the symmetry and symmetry-breaking properties of the solutions, and about their nodal domains. Our results include new multiplicity results for the Brezis-Nirenberg problem −Δu+λu=|u|^2*−2u in Ω, u=0 on ∂Ω.     

Existence of positive solutions for the Hénon equation involving critical Sobolev terms

Let N?3, ^2*=2N/(N−2) and Ω⊂RN be a bounded domain with a smooth boundary ∂Ω and 0∈Ω. Our purpose in this paper is to consider the existence of solutions of Hénon equation:

     

A sparse counterpart of Reichel and Gragg’s package QRUP

We describe how to maintain the triangular factor of a sparse QR factorization when columns are added and deleted and Q cannot be stored for sparsity reasons. The updating procedures could be thought of as a sparse counterpart of Reichel and Gragg’s package QRUP. They allow us to solve a sequence of sparse linear least squares subproblems in which each matrix B_k is an independent subset of the columns of a fixed matrix A, and B_k+1 is obtained by adding or deleting one column. Like Coleman and Hulbert [T. Coleman, L. Hulbert, A direct active set algorithm for large sparse quadratic programs with simple bounds, Math. Program. 45 (1989) 373-406], we adapt the sparse direct methodology of Björck and Oreborn of the late 1980s, but without forming A^TA, which may be only positive semidefinite. Our Matlab 5 implementation works with a suitable row and column numbering within a static triangular sparsity pattern that is computed in advance by symbolic factorization of A^TA and preserved with placeholders.     

Invariance principles for stochastic area and related stochastic integrals

Given an antisymmetric kernel K (K(z, z′) = ?K(z′, z)) and i.i.d. random variates Z_n, n?1, such that EK²(Z₁, Z₂)<∞, set A_n = ∑₁?i?j?nK(Z_i,Z_j), n?1. If the Z_n's are two-dimensional and K is the determinant function, A_n is a discrete analogue of Paul Lévy's so-called stochastic area. Using a general functional central limit theorem for stochastic integrals, we obtain limit theorems for the A_n's which mirror the corresponding results for the symmetric kernels that figure in theory of U-statistics.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

Exit time and invariant measure asymptotics for small noise constrained diffusions

Constrained diffusions, with diffusion matrix scaled by small ?>0, in a convex polyhedral cone G⊂R^k, are considered. Under suitable stability assumptions small noise asymptotic properties of invariant measures and exit times from domains are studied. Let B⊂G be a bounded domain. Under conditions, an “exponential leveling” property that says that, as ?→0, the moments of functionals of exit location from B, corresponding to distinct initial conditions, coalesce asymptotically at an exponential rate, is established. It is shown that, with appropriate conditions, difference of moments of a typical exit time functional with a sub-logarithmic growth, for distinct initial conditions in suitable compact subsets of B, is asymptotically bounded. Furthermore, as initial conditions approach 0 at a rate ?² these moments are shown to asymptotically coalesce at an exponential rate.     

Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system

In this paper, we study a scalar conservation law that models a highly re-entrant manufacturing system as encountered in semi-conductor production. As a generalization of Coron et al. (2010) [14], the velocity function possesses both the local and nonlocal character. We prove the existence and uniqueness of the weak solution to the Cauchy problem with initial and boundary data in L^∞. We also obtain the stability (continuous dependence) of both the solution and the out-flux with respect to the initial and boundary data. Finally, we prove the existence of an optimal control that minimizes, in the Lp-sense with 1?p?∞, the difference between the actual out-flux and a forecast demand over a fixed time period.     

Banach algebras of structured matrix sequences

We discuss the asymptotic behavior of matrix sequences belonging to a special class of non-commutative Banach algebras and study, in particular, the stability, and more general the Fredholm property of such sequences. The abstract results are applied to finite sections of band-dominated operators, especially in the case l^p(Z), 1?p?∞.     

Entire solutions for a semilinear fourth order elliptic problem with exponential nonlinearity

We investigate entire radial solutions of the semilinear biharmonic equation Δ²u=λexp(u) in Rn, n?5, λ>0 being a parameter. We show that singular radial solutions of the corresponding Dirichlet problem in the unit ball cannot be extended as solutions of the equation to the whole of Rn. In particular, they cannot be expanded as power series in the natural variable s=log|x|. Next, we prove the existence of infinitely many entire regular radial solutions. They all diverge to −∞ as |x|→∞ and we specify their asymptotic behaviour. As in the case with power-type nonlinearities [F. Gazzola, H.-Ch. Grunau, Radial entire solutions for supercritical biharmonic equations, Math. Ann. 334 (2006) 905-936], the entire singular solution x?−4log|x| plays the role of a separatrix in the bifurcation picture. Finally, a technique for the computer assisted study of a broad class of equations is developed. It is applied to obtain a computer assisted proof of the underlying dynamical behaviour for the bifurcation diagram of a corresponding autonomous system of ODEs, in the case n=5.     

L1 regularization method in electrical impedance tomography by using the L1-curve (Pareto frontier curve)

Electrical impedance tomography (EIT), as an inverse problem, aims to calculate the internal conductivity distribution at the interior of an object from current-voltage measurements on its boundary. Many inverse problems are ill-posed, since the measurement data are limited and imperfect. To overcome ill-posedness in EIT, two main types of regularization techniques are widely used. One is categorized as the projection methods, such as truncated singular value decomposition (SVD or TSVD). The other categorized as penalty methods, such as Tikhonov regularization, and total variation methods. For both of these methods, a good regularization parameter should yield a fair balance between the perturbation error and regularized solution. In this paper a new method combining the least absolute shrinkage and selection operator (LASSO) and the basis pursuit denoising (BPDN) is introduced for EIT. For choosing the optimum regularization we use the L1-curve (Pareto frontier curve) which is similar to the L-curve used in optimising L2-norm problems. In the L1-curve we use the L1-norm of the solution instead of the L2 norm. The results are compared with the TSVD regularization method where the best regularization parameters are selected by observing the Picard condition and minimizing generalized cross validation (GCV) function. We show that this method yields a good regularization parameter corresponding to a regularized solution. Also, in situations where little is known about the noise level σ, it is also useful to visualize the L1-curve in order to understand the trade-offs between the norms of the residual and the solution. This method gives us a means to control the sparsity and filtering of the ill-posed EIT problem. Tracing this curve for the optimum solution can decrease the number of iterations by three times in comparison with using LASSO or BPDN separately.     

Existence of radial solutions with prescribed number of zeros for elliptic equations and their Morse index

In this paper we consider radially symmetric solutions of the nonlinear Dirichlet problem Δu+f(|x|,u)=0 in Ω, where Ω is a ball in RN, N?3 and f satisfies some appropriate assumptions. We prove existence of radially symmetric solutions with k prescribed number of zeros. Moreover, when f(|x|,u)=K(|x|)|u|^p−1u, using the uniqueness result due to Tanaka (2008) [21], we verify that these solutions are non-degenerate and we prove that their radial Morse index is exactly k.     

Regularity for a Schrödinger equation with singular potentials and application to bilinear optimal control

We study the Schrödinger equation i∂_tu+Δu+V₀u+V₁u=0 on R³×(0,T), where V₀(x,t)=|x-a(t)|^-1, with a∈W^2,1(0,T;R³), is a coulombian potential, singular at finite distance, and V₁ is an electric potential, possibly unbounded. The initial condition u₀∈H²(R³) is such that . The potential V₁ is also real valued and may depend on space and time variables. We prove that if V₁ is regular enough and at most quadratic at infinity, this problem is well-posed and the regularity of the initial data is conserved for the solution. We also give an application to the bilinear optimal control of the solution through the electric potential.     

Galerkin/Runge–Kutta discretizations of nonlinear parabolic equations

Global error bounds are derived for full Galerkin/Runge–Kutta discretizations of nonlinear parabolic problems, including the evolution governed by the p  -Laplacian with p?2$p?2$. The analysis presented here is not based on linearization procedures, but on the fully nonlinear framework of logarithmic Lipschitz constants and an extended B  -convergence theory. The global error is bounded in _L2$L_2$ by Δx^r/2+Δt^q$\mathrm{\Delta }{x}^{r/2}+\mathrm{\Delta }{t}^q$, where r is the convergence order of the Galerkin method applied to the underlying stationary problem and q is the stiff order of the algebraically stable Runge–Kutta method.     

Realization of prescribed patterns in the competition model

We demonstrate that for any prescribed set of finitely many disjoint closed subdomains D₁,…,D_m of a given spatial domain Ω in R^N, if d₁,d₂,a₁,a₂,c,d,e are positive continuous functions on Ω and b(x) is identically zero on D?D₁∪?∪D_m and positive in the rest of Ω, then for suitable choices of the parameters λ, μ and all small ε>0, the competition model

     

Smoothness of the carrying simplex for discrete-time competitive dynamical systems: A characterization of neat embedding

The paper is concerned with the question of smoothness of the carrying simplex S for a discrete-time dissipative competitive dynamical system. We give a necessary and sufficient criterion for S being a C¹ submanifold-with-corners neatly embedded in the nonnegative orthant, formulated in terms of inequalities between Lyapunov exponents for ergodic measures supported on the boundary of the orthant. This completes one thread of investigation occasioned by a question posed by M.W. Hirsch in 1988. Besides, amenable conditions are presented to guarantee the Cr (r?1) smoothness of S in the time-periodic competitive Kolmogorov systems of ODEs. Examples are also presented, one in which S is of class C¹ but not neatly embedded, the other in which S is not of class C¹.