Iteratively reweighted least squares minimization for sparse recovery

Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (where m < N), vectors x ∈ ?^N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φx even though Φ^?1(y) is typically an (N ? m)—dimensional hyperplane; in addition, x is then equal to the element in Φ^?1(y) of minimal ??₁‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Φ^?1(y) with smallest ??₂(w)‐norm. If x⁽ⁿ⁾ is the solution at iteration step n, then the new weight w⁽ⁿ⁾ is defined by w := [|x|² + ε]^?1/2, i = 1, …, N, for a decreasing sequence of adaptively defined ε_n; this updated weight is then used to obtain x^{(n + 1)} and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x⁽ⁿ⁾ converges for all y, regardless of whether Φ^?1(y) contains a sparse vector. If there is a sparse vector in Φ^?1(y), then the limit is this sparse vector, and when x⁽ⁿ⁾ is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight w = [|x|² + ε]^?1+τ/2, i = 1, …, N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.     

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On the minimum size of tight hypergraphs

A k-graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ? E sicj tjat f|_α is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number ? of edges in a tight k-graph with n vertices are given. We conjecture that ? for every n and prove the equality when 2n + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.     

Non-linear parabolic problem associated with the penetration of a magnetic field into a substance

We study the following initial and boundary value problem: In section 1, with u₀ in L²(Ω), f continuous such that f(u) + ? non-decreasing for ? positive, we prove the existence of a unique solution on (0,T), for each T > 0. In section 2 it is proved that the unique soluition u belongs to L²(0, T; H ∩ H²) ∩ L^∞(0, T; H) if we assume u₀ in H and f in C¹(?,?). Numerical results are given for these two cases.     

A generalization of a result of Tran Van Trung on t-designs

We prove that if there exists a t − (v, k, λ) design satisfying the inequality for some positive integer j (where m = min{j, v − k} and n = min {i, t}), then there exists a t − (v + j, k, λ ()) design. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 107–112, 1999     

Resonance phenomena for a class of partial differential equations of higher order in cylindrical waveguides

We consider a domain Ω in ?ⁿ of the form Ω = ?^l × Ω′ with bounded Ω′ ? ?^n?l. In Ω we study the Dirichlet initial and boundary value problem for the equation ? u + [(? ? ?… ? ?)^m + (? ? ?… ? ?)^m]u = fe^?iωt. We show that resonances can occur if 2m ≥ l. In particular, the amplitude of u may increase like t^α (α rational, 0<α<1) or like in t as t∞∞. Furthermore, we prove that the limiting amplitude principle holds in the remaining cases.     

Tangential Convergence of Temperatures and Harmonic Functions in Besov and in Triebel-Lizorkin Spaces

We study the maximal function Mf(x) = sup |f(x + y, t)| when Ω is a region in the (y,t) Ω upper half space R and f(x, t) is the harmonic extension to R₊^N+1 of a distribution in the Besov space B^α_p,q(R^N) or in the Triebel-Lizorkin space F^α_p,q(R^N). In particular, we prove that when Ω= {|_y|^{N/ (N-αp)} < t < 1} the operator M is bounded from F (R^N) into L^p (R^N). The admissible regions for the spaces B (R^N) with p < q are more complicated.     

m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements

It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector X_n = ^t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (X_n ? nX)/n ? ρ(C cos(τ₂log n + φ) + S sin(τ₂log n + φ)) →_n→∞ 0 almost surely and in L²; σ₂ and τ₂ denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Compactness methods in the theory of homogenization II: Equations in non-divergence form

We prove C^{0, α}, C^{1, α} and C^{1, 1} a priori estimates for solutions of boundary value problems for elliptic operators with periodic coefficients of the form Σ,^j=1a^{i j}(x/?)δ²/δx_iδx_j. The constants in these estimates are independent of the small parameter ?, and hence our results imply strengthened versions of the classical averaging theorems. These results generalize to a wide class of linear operators in non-divergence form, including equations with lower-order terms and nonuniformly oscillating coefficients, as well as to certain nonlinear problems, which we discuss in the last section.     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators I

In this paper we study weighted function spaces of type B(?ⁿ, Q(x)) and F(?ⁿ, Q(x)), where Q(x) is a weight function of at most polynomial growth. Of special interest are the weight functions Q(x) = (1 + |x|²)^α/2 with α ? ?. The main result deals with estimates for the entropy numbers of compact embeddings between spaces of this type.     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

Monotone numerical schemes for a Dirichlet problem for elliptic operators in divergence form

We consider a second‐order differential operator A( x )=?∑?_ia_ij( x )?_j+ ∑?_j(b_j( x )·)+c( x ) on ?^d, on a bounded domain D with Dirichlet boundary conditions on ?D, under mild assumptions on the coefficients of the diffusion tensor a_ij. The object is to construct monotone numerical schemes to approximate the solution of the problem A( x )u( x )=µ( x ), x ∈D, where µ is a positive Radon measure. We start by briefly mentioning questions of existence and uniqueness introducing function spaces needed to prove convergence results. Then, we define non‐standard stencils on grid‐knots that lead to extended discretization schemes by matrices possessing compartmental structure. We proceed to discretization of elliptic operators, starting with constant diffusion tensor and ending with operators in divergence form. Finally, we discuss W‐convergence in detail, and mention convergence in C and L₁ spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.     

Function Spaces with Exponential Weights II

This paper is a continuation of [8]. We study weighted function spaces of type B and F on the Euclidean space Rⁿ, where u is a weight function of at most exponential growth. In particular, u(χ (±|χ|) is an admissible weight. We deal with atomic decompositions of these spaces. Furthermore, we prove that the spaces B and F are isomorphic to the corresponding unweighted spaces B and F.     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators II

This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?ⁿ, w(x)) and F (?ⁿ, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b₂(x) b(x, D) b₁(x), where b₁(x) and b₂(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L₂.     

On the well‐posedness of the Cauchy problem for an MHD system in Besov spaces

This paper is devoted to the study of the Cauchy problem of incompressible magneto‐hydrodynamics system in the framework of Besov spaces. In the case of spatial dimension n?3, we establish the global well‐posedness of the Cauchy problem of an incompressible magneto‐hydrodynamics system for small data and the local one for large data in the Besov space ? (?ⁿ), 1?p<∞ and 1?r?∞. Meanwhile, we also prove the weak–strong uniqueness of solutions with data in ? (?ⁿ)∩L²(?ⁿ) for n/2p+2/r>1. In the case of n=2, we establish the global well‐posedness of solutions for large initial data in homogeneous Besov space ? (?²) for 2<p<∞ and 1?r<∞. Copyright © 2008 John Wiley & Sons, Ltd.     

Boltzmann diffusive limit beyond the Navier‐Stokes approximation

Given a normalized Maxwellian μ and n ≥ 1, we establish the global‐in‐time validity of a diffusive expansion for a solution F^ε to the rescaled Boltzmann equation (diffusive scaling) inside a periodic box ??³. We assume that in the initial expansion (0.1) at t = 0, the fluid parts of these f_m(0,x,v) have arbitrary divergence‐free velocity fields as well as temperature fields for all 1 ≤ m ≤ n while f₁(0,x,v) has small amplitude in H². For m ≥ 2, these f_m(t,x,v) are determined by a sequence of linear Navier‐Stokes‐Fourier systems iteratively. More importantly, the remainder f(t,x,v) is proven to decay in time uniformly in ε via a unified nonlinear energy method. In particular, our results lead to an error estimate for f₁(t,x,v), the well‐known Navier‐Stokes‐Fourier approximation, and beyond. The collision kernel Q includes hard‐sphere, the cutoff inverse‐power, as well as the Coulomb interactions. © 2005 Wiley Periodicals, Inc.     

On invariant measures of extensions of Markov transition functions

By using the LITTLEWOOD matrices A_2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A_2n: l(L_P) → l(L_P)‖ completely. The result is compared with the norms ‖A_2n: l → l‖, which are calculated implicitly in PIETSCH [6].     

On series of signed vectors and their rearrangements

Let x₁,…,x_m∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥x_i∥₂ ≤ 1 for all i. It is proved that there are signs ε₁,…,ε_m = ±1 such that where C₁, C₂ are some numerical constants. It is also proved that there are signs ε,…,ε = ±1 and a permutation π of {1,…,m} such that where C^′ is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On the number of interior peak solutions for a singularly perturbed Neumann problem

We consider the following singularly perturbed Neumann problem: where Δ = Σ ?²/?x is the Laplace operator, ? > 0 is a constant, Ω is a bounded, smooth domain in ?^N with its unit outward normal ν, and f is superlinear and subcritical. A typical f is f(u) = u^p where 1 < p < +∞ when N = 2 and 1 < p < (N + 2)/(N ? 2) when N ≥ 3. We show that there exists an ?₀ > 0 such that for 0 < ? < ?₀ and for each integer K bounded by where α_{N, Ω, f} is a constant depending on N, Ω, and f only, there exists a solution with K interior peaks. (An explicit formula for α_{N, Ω, f} is also given.) As a consequence, we obtain that for ? sufficiently small, there exists at least [α_{N, Ωf}/?^N (|ln ?|)^N] number of solutions. Moreover, for each m ∈ (0, N) there exist solutions with energies in the order of ?^N?m. © 2006 Wiley Periodicals, Inc.     

Asymptotic characterization of standing waves and of the static limit for a class of wave equations of higher order with a variable coefficient and time-independent incitation

We consider the equation (?1)^m?^m (p?^mu) + ?u = ? in ?ⁿ × (0, ∞) for arbitrary positive integers m and n and under the assumptions p ? 1, ? ? C(?ⁿ) and p > 0. Even if the differential operator (?1)^m?^m (p?^mu) has no eigenvalues, the solution u(x,t) may increase as t → ∞ for 2m ≥ n. For this case, we derive necessary and sufficient conditions for the convergence of u(x,t) as t → ∞. Furthermore, we characterize the functions occurring in these conditions as solutions of the homogeneous static equation (?1)^m?^m (p?^mu) = 0, which satisfy appropriate asymptotic conditions at infinity. We also give an asymptotic characterization of the static limit.