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.     

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.     

Generalized induced norms

Let ‖·‖ be a norm on the algebra ?_n of all n × n matrices over ?. An interesting problem in matrix theory is that “Are there two norms ‖·‖₁ and ‖·‖₂ on ?_n such that ‖A‖ = max|‖Ax‖₂: ‖x‖₁ = 1} for all A ∈ ?_n?” We will investigate this problem and its various aspects and will discuss some conditions under which ‖·‖₁ = ‖·‖₂.     

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)     

On Σ1-definable Functions Provably Total in I ∏

We prove the following theorem: Let φ(x) be a formula in the language of the theory PA^? of discretely ordered commutative rings with unit of the form ?yφ′(x,y) with φ′ and let ∈ Δ₀ and let fφ: ? → ? such that f_φ(x) = y iff φ′(x,y) & (?z < y) φ′(x,z). If I ∏ ∈(?x ≥ 0), φ then there exists a natural number K such that I ∏ ? ?y?x(x > y ? ?φ(x) < x^K). Here I ∏₁^? denotes the theory PA^? plus the scheme of induction for formulas φ(x) of the form ?yφ′(x,y) (with φ′) with φ′ ∈ Δ₀.     

The Ptolemy and Zb?ganu constants of normed spaces

In every inner product space H the Ptolemy inequality holds: the product of the diagonals of a quadrilateral is less than or equal to the sum of the products of the opposite sides. In other words, ‖x−y‖‖z−w‖≤‖x−z‖‖y−w‖+‖z−y‖‖x−w‖ for any points w,x,y,z in H. It is known that for each normed space (X,‖⋅‖), there exists a constant C such that for any w,x,y,z∈X, we have ‖x−y‖‖z−w‖≤C(‖x−z‖‖y−w‖+‖z−y‖‖x−w‖). The smallest such C is called the Ptolemy constant of X and is denoted by C_P(X). We study the relationships between this constant and the geometry of the space X, and hence with metric fixed point theory. In particular, we relate the Ptolemy constant C_P to the Zb?ganu constant C_Z, and prove that if X is a Banach space with , then X has (uniform) normal structure and therefore the fixed point property for nonexpansive mappings. We derive general lower and upper bounds for both C_P and C_Z, and calculate the precise values of these two constants for several normed spaces. We also present a number of conjectures and open problems.     

Stable signal recovery from incomplete and inaccurate measurements

Suppose we wish to recover a vector x₀ ∈ ?^?? (e.g., a digital signal or image) from incomplete and contaminated observations y = A x₀ + e; A is an ?? × ?? matrix with far fewer rows than columns (?? ? ??) and e is an error term. Is it possible to recover x₀ accurately based on the data y? To recover x₀, we consider the solution x^# to the ??₁‐regularization problem where ? is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x₀ is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A's provided that the number of nonzeros of x₀ is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x₀; then stable recovery occurs for almost any set of ?? coefficients provided that the number of nonzeros is of the order of ??/(log ??)⁶. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.     

Dynamics of a three‐dimensional systems of rational difference equations

We investigate in this paper the solutions and the periodicity of the following rational systems of difference equations of three‐dimensional with initial conditions x_?2,x_?1,x₀,y_?2,y_?1,y₀,z_?2,z_?1andz₀ are nonzero real numbers. Copyright © 2015 John Wiley & Sons, Ltd.     

Finitely strictly singular operators between James spaces

An operator between Banach spaces is said to be finitely strictly singular if for every ε>0 there exists n such that every subspace E⊆X with dimE?n contains a vector x such that ‖Tx‖<ε‖x‖. We show that, for 1?p<q<∞, the formal inclusion operator from Jp to Jq is finitely strictly singular. As a consequence, we obtain that the strictly singular operator with no invariant subspaces constructed by C. Read is actually finitely strictly singular. These results are deduced from the following fact: if k?n then every k-dimensional subspace of Rn contains a vector x with ‖x?_∞‖=1 such that xmi=i(−1) for some m₁<?<mk.     

Strong solutions to the Keller‐Segel system with the weak Ln /2 initial data and its application to the blow‐up rate

We shall show an exact time interval for the existence of local strong solutions to the Keller‐Segel system with the initial data u₀ in L^{n /2}_w (?ⁿ), the weak L^{n /2}‐space on ?ⁿ. If ‖u₀‖ is sufficiently small, then our solution exists globally in time. Our motivation to construct solutions in L^{n /2}_w (?ⁿ) stems from obtaining a self‐similar solution which does not belong to any usual L^p(?ⁿ). Furthermore, the characterization of local existence of solutions gives us an explicit blow‐up rate of ‖u (t)‖ for n /2 < p < ∞ as t → T_max, where T_max denotes the maximal existence time (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

The spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups

A ternary quasigroup (or 3‐quasigroup) is a pair (N, q) where N is an n‐set and q(x, y, z) is a ternary operation on N with unique solvability. A 3‐quasigroup is called 2‐idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x)=y. A conjugation of a 3‐quasigroup, considered as an OA(3, 4, n), $({{N}},{\mathcal{B}})$, is a permutation of the coordinate positions applied to the 4‐tuples of ${\mathcal{B}}$. The subgroup of conjugations under which $({{N}},{\mathcal{B}})$ is invariant is called the conjugate invariant subgroup of $({{N}},{\mathcal{B}})$. In this article, we determined the existence of 2‐idempotent 3‐quasigroups of order n, n≡7 or 11 (mod 12) and n≥11, with conjugate invariant subgroup consisting of a single cycle of length three. This result completely determined the spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups. As a corollary, we proved that an overlarge set of Mendelsohn triple system of order n exists if and only if n≡0, 1 (mod 3) and n≠6. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 292–304, 2010     

On an Ingelstam's Theorem

A well-known Ingelstam's Theorem asserts that every real Hilbert space A with an associative unital product satisfying ‖ xy‖ ≤ ‖ x‖ ‖ y‖ and ‖ 1‖ = 1 is isomorphic to the reals ?, or the complex numbers ?, or the quaternions ?. This note deals with a nonunital and nonassociative extension of the Ingelstam Theorem. So the assumptions about associativity and existence of unity are weakened to the existence of a nonzero central idempotent e such that ‖ ex‖ = ‖e‖ ‖ x‖ for all x, and that in A holds a determined kind of algebraic identity strictly weaker that alternativeness. We prove that, up to isomorphisms, there are only seven algebras satisfying these assumptions, even without the requirement of completeness. On the other hand, Section 3 presents another characterization of the obtained algebras with the flavor of one of the main theorems in Bhatt et al. (1998 Bhatt , S. J. , Karia , D. J. , Kulkarni , S. H. , Shimpi , M. E. ( 1998 ). A note on the Gelfand-Mazur theorem . Proc. Amer. Math. Soc. 126 ( 10 ): 2999 – 3005 .[Crossref], [Web of Science ®] , [Google Scholar]).     

On exact recovery of sparse vectors from linear measurements

Let 1 ≤ k ≤ n < N. We say that a vector x ∈ ? ^N is k-sparse if it has at most k nonzero coordinates. Let Φ be an n × N matrix. We consider the problem of recovery of a k-sparse vector x ∈ ? ^N from the vector y = Φx ∈ ? ⁿ . We obtain almost-sharp necessary conditions for k, n, N for this problem to be reduced to that of minimization of the ?₁-norm of vectors z satisfying the condition y = Φz.     

A Quantitative Version of the Bishop–Phelps Theorem for Operators in Hilbert Spaces

In this paper, with the help of spectral integral, we show a quantitative version of the Bishop-Phelps theorem for operators in complex Hilbert spaces. Precisely, let H be a complex Hilbert space and 0 ε 1/2. Then for every bounded linear operator T : H → H and x0 ∈ H with ||T|| = 1 = ||x0|| such that ||Tx0|| 1 ε, there exist xε∈ H and a bounded linear operator S : H → H with||S|| = 1 = ||xε|| such that ||Sxε|| = 1, ||xε-x0|| ≤ (2ε)1/2 + 4(2ε)1/2, ||S-T|| ≤(2ε)1/2.     

A note on feebly continuous functions

A function f from to is said to be feebly continuous at a point (x,y) if there exist sequences x_nx and y_ny with lim_n→∞lim_m→∞f(x_n,y_m)=f(x,y). Dales asked if every function has a point of feeble continuity. Our aim in this short note is to show that (assuming the Continuum Hypothesis) the answer is ‘no’. Dales also asked what happens for functions taking only two values: we show that in this case the answer is ‘yes’.     

Distance Functions and Almost Global Solutions of Eikonal Equations

Consider a function u defined on  ⁿ , except, perhaps, on a closed set of potential singularities . Suppose that u solves the eikonal equation ‖Du‖ = 1 in the pointwise sense on  ⁿ \, where Du denotes the gradient of u and ‖·‖ is a norm on  ⁿ with the dual norm ‖·‖_?. For a class of norms which includes the standard p-norms on  ⁿ , 1 < p < ∞, we show that if  has Hausdorff 1-measure zero and n ≥ 2, then u is either affine or a “cone function,” that is, a function of the form u(x) = a ± ‖x ? z‖_?.     

Rational approximations for the cosine function; P-acceptability and order

Properties of order stars corresponding to rational approximations for cos z are derived and are used to prove that the order of accuracy of a P-acceptable approximantR _nm(z ²), with numerator of degreen and denominator of degreem, cannot exceed 2m. It is shown that if the poles ofR _nm(z ²) are restricted to pure-imaginary values ofz the maximum attainable order is 2n+2, whatever the value ofm1. A study of rational approximations for the cosine function produced by symmetric one-step collocation methods, applied to the differential equationy ⁿ =–² y, provides the answer to a question posed by Kramarz [BIT 20 (1980) 215–222]; there are no P-stable methods of that type.     

A connection between Schur multiplication and Fourier interpolation. II

Given m × n matrices A = [a_jk ] and B = [b_jk ], their Schur product is the m × n matrix A ○ B = [a_jkb_jk ]. For any matrix T, define ‖T‖ _S = max_{X ≠O} ‖T ○ X ‖/‖X ‖ (where ‖·‖ denotes the usual matrix norm). For any complex (2n – 1)‐tuple μ = (μ _{–n +1}, μ _{–n +2}, …, μ _{n –1}), let T_μ be the Hankel matrix [μ –_{n +j +k –1}]_j,k and define ??_μ = {f ∈ L ₁[–π, π] : f? (2j ) = μ_j for –n + 1 ≤ j ≤ n – 1} . It is known that ‖T_μ‖ _S ≤ infequation/tex2gif-inf-18.gif ‖f ‖₁. When equality holds, we say T_μ is distinguished. Suppose now that μ _j ∈ ? for all j and hence that T_μ is hermitian. Then there is a real n × n hermitian unitary X and a real unit vector y such that 〈(T_μ ○ X )y, y 〉 = ‖T_μ ‖_S . We call such a pair a norming pair for T_μ . In this paper, we study norming pairs for real Hankel matrices. Specifically, we characterize the pairs that norm some distinguished Schur multiplier T_μ . We do this by giving necessary and suf.cient conditions for (X, y ) to be a norming pair in the n ‐dimensional case. We then consider the 2‐ and 3‐dimensional cases and obtain further results. These include a new and simpler proof that all real 2 × 2 Hankel matrices are distinguished, and the identi.cation of new classes of 3 × 3 distinguished matrices. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)