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.     

For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

We consider linear equations y = Φx where y is a given vector in ?ⁿ and Φ is a given n × m matrix with n < m ≤ τn, and we wish to solve for x ∈ ?^m. We suppose that the columns of Φ are normalized to the unit ??₂‐norm, and we place uniform measure on such Φ. We prove the existence of ρ = ρ(τ) > 0 so that for large n and for all Φ's except a negligible fraction, the following property holds: For every y having a representation y = Φx₀ by a coefficient vector x₀ ∈ ?^m with fewer than ρ · n nonzeros, the solution x₁ of the ??₁‐minimization problem is unique and equal to x₀. In contrast, heuristic attempts to sparsely solve such systems—greedy algorithms and thresholding—perform poorly in this challenging setting. The techniques include the use of random proportional embeddings and almost‐spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices. © 2006 Wiley Periodicals, Inc.     

On the form of homomorphisms into the differential group Ls 1 and their extensibility

Let L_s ¹ (s ∈ ?) be the s-th differential group, that is the set {(x1,…,x_s): x₁ ≠ 0, x_n ∈ K, n =1,2,…,s} (K ∈ {?,?}) together with the group operation which describes the chain rules (up to order s) for C^s-functions with fixed point 0. We consider homomorphisms Φ_s, Φ_s = (f₁,…,f_s) from an abelian group (G,+) into L_s ¹ such that f₁ = 1, f₂ = … = f_p+2 = 0, 0_p+2 ≠ 0 for a fixed, but arbitrary p ≥ 0 such that p + 2 ≤ s (then f_p+2 is necessarily a homomorphism from (G, +) to (K, +). Let l ∈ ? or l = ∞. We present a criterion for the extensibility of Φ_s to a homomorphism Φ_s+l from (G, +) to L_s+1 ¹ (L_∞ ¹, if l = ∞), by proving that such an extension (continuation) exists iff the component functions f_n of Φ_s with s - p ≤ n ≤ min(s - p + l - 1,s) are certain polynomials in f_P+2 (see Theorem 1). We also formulate the problem in the language of truncated formal power series in one indeterminate X over K. The somewhat easier situation f ₁ ≠ 1 will be studied in a separate paper.     

Congruent elliptic curves with non-trivial Shafarevich-Tate groups: Distribution part

Given a large positive number x and a positive integer k, we denote by Qk(x) the set of congruent elliptic curves E(n): y2= z3- n2 z with positive square-free integers n x congruent to one modulo eight,having k prime factors and each prime factor congruent to one modulo four. We obtain the asymptotic formula for the number of congruent elliptic curves E(n)∈ Qk(x) with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)2. We also get a lower bound for the number of E(n)∈ Qk(x)with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)4. The key ingredient of the proof of these results is an independence property of residue symbols. This property roughly says that the number of positive square-free integers n x with k prime factors and residue symbols(quadratic and quartic) among its prime factors being given compatible values does not depend on the actual values.     

Planar Graded Lattices and the <Emphasis Type="Bold">c</Emphasis><Subscript>1</Subscript>-Median Property

Let L be a lattice of finite length, ξ = (x ₁,…, x _k )∈L ^k , and y ∈ L. The remoteness r(y, ξ) of y from ξ is d(y, x ₁)+?+d(y, x _k ), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice. We prove that whenever r(y, ξ) ≤ r(z, ξ) for all z ∈ L, then y ≤ x ₁∨?∨x _k . In other words, L satisfies the so-called c ₁ -median property.     

On the number of coprime integral solutions of y2 = x3 + k

Let N′(k) denote the number of coprime integral solutions x, y of y² = x³ + k. It is shown that lim sup_k→∞N′(k) ≥ 12.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Approximation algorithms for indefinite complex quadratic maximization problems

In this paper,we consider the following indefinite complex quadratic maximization problem: maximize zHQz,subject to zk ∈ C and zkm = 1,k = 1,...,n,where Q is a Hermitian matrix with trQ = 0,z ∈ Cn is the decision vector,and m 3.An (1/log n) approximation algorithm is presented for such problem.Furthermore,we consider the above problem where the objective matrix Q is in bilinear form,in which case a 0.7118 cos mπ 2approximation algorithm can be constructed.In the context of quadratic optimization,various extensions and connections of the model are discussed.     

On the Rédei zeta function

Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ?(s; L) = Σ_x∈Lμ(Ô, x) ν(Ô, x)^?s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.     

Solving exponential diophantine equations using lattice Basis Reduction Algorithms

Let S be the set of all positive integers with prime divisors from a fixed finite set of primes. Algorithms are given for solving the diophantine inequality 0< x − y < y^δ in x, y ∈ S for fixed δ ∈ (0, 1), and for the diophantine equation x + y = z in x, y, z ∈ S. The method is based on multi-dimensional diophantine approximation, in the real and p-adic case, respectively. The main computational tool is the L³-Basis Reduction Algorithm. Elaborate examples are presented.     

Analytic extension of non quasi-analytic Whitney jets of Roumieu type

Let (M_r)_{r∈? 0} be a logarithmically convex sequence of positive numbers which verifies M₀ = 1 as well as M_r ≥ 1 for every r ∈ ? and defines a non quasi-analytic class. Let moreover F be a closed proper subset of ?ⁿ. Then for every function ? on ?ⁿ belonging to the non quasi-analytic (M_r)-class of Roumieu type, there is an element g of the same class which is analytic on ?ⁿ F and such that D^α ?(x) = D^αg(x) for every σ ∈ ?₀ ⁿ SBAP and x ∈ F.     

Quasi‐symmetric designs with fixed difference of block intersection numbers

The following results for proper quasi‐symmetric designs with non‐zero intersection numbers x,y and λ > 1 are proved.

• (1) Let D be a quasi‐symmetric design with z = y ? x and v ≥ 2k. If x ≥ 1 + z + z³ then λ < x + 1 + z + z³.
• (2) Let D be a quasi‐symmetric design with intersection numbers x, y and y ? x = 1. Then D is a design with parameters v = (1 + m) (2 + m)/2, b = (2 + m) (3 + m)/2, r = m + 3, k = m + 1, λ = 2, x = 1, y = 2 and m = 2,3,… or complement of one of these design or D is a design with parameters v = 5, b = 10, r = 6, k = 3, λ = 3, and x = 1, y = 2.
• (3) Let D be a triangle free quasi‐symmetric design with z = y ? x and v ≥ 2k, then x ≤ z + z².
• (4) For fixed z ≥ 1 there exist finitely many triangle free quasi‐symmetric designs non‐zero intersection numbers x, y = x + z.
• (5) There do not exist triangle free quasi‐symmetric designs with non‐zero intersection numbers x, y = x + 2.

© 2006 Wiley Periodicals, Inc. J Combin Designs 15: 49–60, 2007     

Copositive pointwise approximation

We prove that if a functionf ∈C ⁽¹⁾ (I),I: = [?1, 1], changes its signs times (s ∈ ?) within the intervalI, then, for everyn > C, whereC is a constant which depends only on the set of points at which the function changes its sign, andk ∈ ?, there exists an algebraic polynomialP _n =P _n (x) of degree ≤n which locally inherits the sign off(x) and satisfies the inequality $$\left| {f\left( x \right) - P_n \left( x \right)} \right| \leqslant c\left( {s,k} \right)\left( {\frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right)\omega _k \left( {f'; \frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right), x \in I$$ , where ω _k (f′;t) is thekth modulus of continuity of the functionf’. It is also shown that iff ∈C (I) andf(x) ≥ 0,x ∈I then, for anyn ≥k ? 1, there exists a polynomialP _n =P _n (x) of degree ≤n such thatP _n (x) ≥ 0,x ∈I, and |f(x) ?P _n (x)| ≤c(k)ω _k (f;n ^?2 +n ^?1 √1 ?x ²),x ∈I.     

Approximation by antiderivatives

Let Ω ?C be an open set with simply connected components and suppose that the functionφ is holomorphic on Ω. We prove the existence of a sequence {φ ^(?n)} ofn-fold antiderivatives (i.e., we haveφ ⁽⁰⁾(z)∶=φ(z) andφ ^(?n)(z)=dφ ^(?n?1)(z)/dz for alln ∈ N₀ and z ∈ Ω) such that the following properties hold:

1. For any compact setB ?Ω with connected complement and any functionf that is continuous onB and holomorphic in its interior, there exists a sequence {n _k} such that {φ^?nk} converges tof uniformly onB.
2. For any open setU ?Ω with simply connected components and any functionf that is holomorphic onU, there exists a sequence {m _k} such that {φ^?mk} converges tof compactly onU.
3. For any measurable setE ?Ω and any functionf that is measurable onE, there exists a sequence {p _k} such that {φ ^(-Pk)} converges tof almost everywhere onE.

     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Almost sure central limit theorem for partial sums and maxima

Let X, X₁, X₂, … be i.i.d. random variables with nondegenerate common distribution function F, satisfying EX = 0, EX² = 1. Let X_i and M_n = max{X_i, 1 ≤ i ≤ n }. Suppose there exists constants a_n > 0, b_n ∈ R and a nondegenrate distribution G (y) such that Then, we have almost surely, where f (x, y) denotes the bounded Lipschitz 1 function and Φ(x) is the standard normal distribution function (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Über Folgen,die BezÜglich Eines Mittels Rekurrent Sind

Let X be a convex subset of a finite-dimensional real vector space. A function M: X ^k → X is called a strict mean value, if M(x₁,…, x_k) lies in the convex hull of x₁,…, x_k), but does not coincide with one of its vertices. A sequence (x_n)_{n∈ ?} in X is called M-recursive if x_n+k = M(x_n, x_n+1,…, x_n+k?1) for all n. We prove that for a continuous strict mean value M every M-recursive sequence is convergent. We give a necessary and sufficient condition for a convergent sequence in X to be M-recursive for some continuous strict mean value M, and we characterize its limit by a functional equation. 39 B 72, 39 B 52, 40 A 05.     

Local solvability of partial differential operators on the Heisenberg group

In this article the following class of partial differential operators is examined for local solvability: Let P(X, Y) be a homogeneous polynomial of degree n ≥ 2 in the non-commuting variables X and Y. Suppose that the complex polynomial P(iz, 1) has distinct roots and that P(z, 0) = zⁿ. The operators which we investigate are of the form P(X, Y) where X = δ_x and Y = δ_y + xδ_w for variables (x, y, w) ∈ ?³. We find that the operators P (X, Y) are locally solvable if and only if the kernels of the ordinary differential operators P(iδ_x, ± x)* contain no Schwartz-class functions other than the zero function. The proof of this theorem involves the construction of a parametrix along with invariance properties of Heisenberg group operators and the application of Sobolev-space inequalities by Hörmander as necessary conditions for local solvability.     

On the equivalence of the Euler-Pommier operators in spaces of analytic functions

In the space A (θ) of all one-valued functions f(z) analytic in an arbitrary region G ? ? (0 ∈ G) with the topology of compact convergence, we establish necessary and sufficient conditions for the equivalence of the operators L ₁=α _n z ⁿ Δ ⁿ + ... + α₁ zΔ+α₀ E and L ₂= z ⁿ a _n (z)Δ ⁿ + ... + za ₁(z)Δ+a ₀(z)E, where δ: (Δ?)(z)=(f(z)-?(0))/z is the Pommier operator in A(G), n ∈ ?, α _n ∈ ?, a _k (z) ∈ A(G), 0≤k≤n, and the following condition is satisfied: Σ _j=s ^n?1 α _j+1 ∈ 0, s=0,1,...,n?1. We also prove that the operators z ^s+1Δ+β(z)E, β(z) ∈ A _R , s ∈ ?, and z ^s+1 are equivalent in the spaces A _R, 0?R?-∞, if and only if β(z) = 0.