Equivalence of Minimal ?0- and ?p-Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p

For a bounded system of linear equalities and inequalities, we show that the NP-hard ℓ ₀-norm minimization problem is completely equivalent to the concave ℓ _p -norm minimization problem, for a sufficiently small p. A local solution to the latter problem can be easily obtained by solving a provably finite number of linear programs. Computational results frequently leading to a global solution of the ℓ ₀-minimization problem and often producing sparser solutions than the corresponding ℓ ₁-solution are given. A similar approach applies to finding minimal ℓ ₀-solutions of linear programs.     

ℓ-Divisibility of ℓ-regular partition functions

We give exact criteria for the ℓ-divisibility of the ℓ-regular partition function b _ℓ (n) for ℓ∈{5,7,11}. These criteria are found using the theory of complex multiplication. In each case the first criterion given corresponds to the Ramanujan congruence modulo ℓ for the unrestricted partition function, and the second is a condition given by J.-P. Serre for the vanishing of the coefficients of ∏ _m=1^∞(1−q ^m ) ^ℓ−1.      

Concerning Bourgain’s ℓ1-Index of a Banach space

A well known argument of James yields that if a Banach spaceX contains ℓ ₁ ⁿ ’s uniformly, thenX contains ℓ ₁ ⁿ ’s almost isometrically. In the first half of the paper we extend this idea to the ordinal ℓ₁-indices of Bourgain. In the second half we use our results to calculate the ℓ₁-index of certain Banach spaces. Furthermore we show that the ℓ₁-index of a separable Banach space not containing ℓ₁ must be of the form ω^α for some countable ordinal α. Research supported by the NSF and TARP.     

On verifiable sufficient conditions for sparse signal recovery via <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript> minimization

We discuss necessary and sufficient conditions for a sensing matrix to be “s-good”—to allow for exact ℓ ₁-recovery of sparse signals with s nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect ℓ ₁-recovery (nonzero measurement noise, nearly s-sparse signal, near-optimal solution of the optimization problem yielding the ℓ ₁-recovery) in terms of the characteristics underlying these conditions. Further, we demonstrate (and this is the principal result of the paper) that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse ℓ ₁-recovery and to efficiently computable upper bounds on those s for which a given sensing matrix is s-good. We establish also instructive links between our approach and the basic concepts of the Compressed Sensing theory, like Restricted Isometry or Restricted Eigenvalue properties.     

Combined ℓ<Subscript>2</Subscript> data and gradient fitting in conjunction with ℓ<Subscript>1</Subscript> regularization

We are interested in minimizing functionals with ℓ₂ data and gradient fitting term and ℓ₁ regularization term with higher order derivatives in a discrete setting. We examine the structure of the solution in 1D by reformulating the original problem into a contact problem which can be solved by dual optimization techniques. The solution turns out to be a ’smooth’ discrete polynomial spline whose knots coincide with the contact points while its counterpart in the contact problem is a discrete version of a spline with higher defect and contact points as knots. In 2D we modify Chambolle’s algorithm to solve the minimization problem with the ℓ₁ norm of interacting second order partial derivatives as regularization term. We show that the algorithm can be implemented efficiently by applying the fast cosine transform. We demonstrate by numerical denoising examples that the ℓ₂ gradient fitting term can be used to avoid both edge blurring and staircasing effects.      

Frames and their associated $\emph{H}_{{\kern-2pt}\emph{F}}^{\emph{p}}$-subspaces

Given a frame F = {f _j } for a separable Hilbert space H, we introduce the linear subspace H^p_FH^{p}_{F} of H consisting of elements whose frame coefficient sequences belong to the ℓ ^p -space, where 1 ≤ p < 2. Our focus is on the general theory of these spaces, and we investigate different aspects of these spaces in relation to reconstructions, p-frames, realizations and dilations. In particular we show that for closed linear subspaces of H, only finite dimensional ones can be realized as H^p_FH^{p}_{F}-spaces for some frame F. We also prove that with a mild decay condition on the frame F the frame expansion of any element in H_F^pH_{F}^{p} converges in both the Hilbert space norm and the ||·|| _{F, p} -norm which is induced by the ℓ ^p -norm.     

Carathéodory balls and norm balls inH n ={z ε ℂ n : ‖z‖1<1}

It is shown that the only balls in the Carathéodory distance onH _n ={z ε ℂ ⁿ :‖z‖₁<1},n≥2, which are balls with respect to the ℓ₁ norm in ℂ ⁿ are those centered at the origin. In memory of Albert Pfluger The research was partially supported by the Fund for the Promotion of Research at the Technion.     

A coordinate gradient descent method for <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript>-regularized convex minimization

In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing ℓ ₁-regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) to solve the more general ℓ ₁-regularized convex minimization problems, i.e., the problem of minimizing an ℓ ₁-regularized convex smooth function. We establish a Q-linear convergence rate for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving large-scale ℓ ₁-regularized linear least squares problems arising in compressed sensing and image deconvolution as well as large-scale ℓ ₁-regularized logistic regression problems for feature selection in data classification. Comparison with several state-of-the-art algorithms specifically designed for solving large-scale ℓ ₁-regularized linear least squares or logistic regression problems suggests that an efficiently implemented CGD method may outperform these algorithms despite the fact that the CGD method is not specifically designed just to solve these special classes of problems.     

Weak* Hypercyclicity and Supercyclicity of Shifts on ℓ∞

We study hypercyclicity and supercyclicity of weighted shifts on ℓ^∞, with respect to the weak * topology. We show that there exist bilateral shifts that are weak * hypercyclic but fail to be weak * sequentially hypercyclic. In the unilateral case, a shift T is weak * hypercyclic if and only if it is weak * sequentially hypercyclic, and this is equivalent to T being either norm, weak, or weak-sequentially hypercyclic on c₀ or ℓ^p (1 ≤ p < ∞). We also show that the set of weak * hypercyclic vectors of any unilateral or bilateral shift on ℓ^∞ is norm nowhere dense. Finally, we show that ℓ^∞ supports an isometry that is weak * sequentially supercyclic.     

Vive la différence III

We show that, consistently, there is an ultrafilter on ω such that if N _n^ℓ = (P _n^ℓ ∪ Q _n^ℓ, P _n^ℓ, Q _n^ℓ, R _n^ℓ) (for ℓ = 1, 2, n < ω), P _n^ℓ ∪ Q _n^ℓ ⊆ ω, and are models of the canonical theory t ^ind of the strong independence property, then every isomorphism from onto is a product isomorphism. The first version of this work done in 93; First typed: May 1993. This research was partially supported by the United States-Israel Binational Science Foundation. Publication 509     

On the variances of a spatial unit root model*

Asymptotic properties of the variances of the spatial autoregressive model X _k,ℓ = αX _k−1,ℓ + βX _k,ℓ−1 + γX _{k−1,ℓ−1} + ε _k,ℓ are investigated in the unit root case, that is, where the parameters are on the boundary of the domain of stability that forms a tetrahedron in [−1, 1]³. The limit of the variance of n ^−ϱ X _[ns],[nt] is determined, where ϱ = 1/4 on the interior of the faces of the domain of stability, ϱ = 1/2 on the edges, and ϱ = 1 on the vertices.     

Isomorphic embeddings and harmonic behaviour of smooth operators

LetY be a Banach space, 1<p<∞. We give a simple criterion for embedding ℓ _p ⊂Y, namely it suffices that the positive cone ℓ _p ⁺ ⊂Y. This result is applied to the study of highly smooth operators from ℓ _p intoY (p is not an even integer). The main result is that every such operator has a harmonic behaviour unless ℓ _p/K ⊂Y for someK ∈ ℕ. Supported by grants GAUK 277/2001, GAČR 201-01-1198, A1019205.     

Hyperspaces of Banach Spaces with the Attouch—Wets Topology

Let X be an infinite-dimensional Banach space with weight τ. By Cld _AW (X), we denote the hyperspace of nonempty closed sets in X with the Attouch—Wets topology. By Fin _AW (X), Comp _AW (X) and Bdd _AW (X), we denote the subspaces of Cld _AW (X) consisting of finite sets, compact sets and bounded closed sets, respectively. In this paper, it is proved that Fin _AW (X)≈Comp _AW (X)≈ℓ₂(τ)×ℓ₂ ^f ℓandℓBdd _AW (X)≈ℓ₂(2^τ)×ℓ₂ ^f where ≈ means ‘is homeomorphic to’, ℓ₂(τ) is the Hilbert space with weight τ (ℓ₂(ℵ₀)=ℓ₂ the separable Hilbert space) and ℓ₂ ^f ={(x _i ) _iεN εℓ₂∣x _i =0 except for finitely many iεN}.     

Schur multiplier characterization of a class of infinite matrices

Let B _w (ℓ ^p ) denote the space of infinite matrices A for which A(x) ∈ ℓ ^p for all x = {x _k } _k=1^∞ ∈ ℓ ^p with |x _k | ↘ 0. We characterize the upper triangular positive matrices from B _w (ℓ ^p ), 1 < p < ∞, by using a special kind of Schur multipliers and the G. Bennett factorization technique. Also some related results are stated and discussed.     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

A homological characterization of hyperbolic groups

A finitely presented group G is hyperbolic iff H ⁽¹⁾ ₁(G,ℝ)=0=⁽¹⁾ ₂(G, ℝ), where H ⁽¹⁾ _* (resp. ⁽¹⁾ _*) denotes the ℓ₁-homology (resp. reduced ℓ₁-homology). If Γ is a graph, then every ℓ₁ 1-cycle in Γ with real coefficients can be approximated by 1-cycles of compact support. A 1-relator group G is hyperbolic iff H ⁽¹⁾ ₁(G,ℝ)=0. Oblatum: 30-IV-1997 & 14-V-1998 / Published online: 14 January 1999     

Biflatness of semigroup algebras

We shall study the biflatness of the convolution algebra ℓ ¹(S) for a semigroup S. We show that for any semigroup S such that ℓ ¹(S) is biflat the canonical partial ordering on the idempotents must be uniformly locally finite. We use this to characterize the biflatness of ℓ ¹(S) for an inverse semigroup S.     

Bernoulli convolutions and an intermediate value theorem for entropies of<Emphasis Type="Italic">K</Emphasis>-partitions

We establish a strong regularity property for the distributions of the random sums Σ±λ ⁿ , known as “infinite Bernoulli convolutions”: For a.e. λ ∃ (1/2, 1) and any fixed ℓ, the conditional distribution of (w _n+1...,w _n+ℓ) given the sum Σ _n=0 ^∞ w _n λ ⁿ , tends to the uniform distribution on {±1}^ℓ asn → ∞. More precise results, where ℓ grows linearly inn, and extensions to other random sums are also obtained. As a corollary, we show that a Bernoulli measure-preserving system of entropyh hasK-partitions of any prescribed conditional entropy in [0,h]. This answers a question of Rokhlin and Sinai from the 1960’s, for the case of Bernoulli systems. The authors were partially supported by NSF grants DMS-9729992 (E. L.), DMS-9803597 (Y. P.) and DMS-0070538 (W. S.).     

A distortion problem for the space ℓ ∞ c (ω 1)

The Banach space ℓ _∞ ^c (ω ₁) is the space of boundedω ₁-sequences of countable support. A pointwise-closed subspaceV≤ℓ _∞ ^c (ω ₁) will be calledunbounded if lcub;min(supp(υ)):υ ∈Vrcub; is unbounded inω ₁. It is shown that there are Lipshitz functionsf: Sph(ℓ _∞ ^c (ω ₁)) → ℝ which have large variation on the unit sphere of any unbounded subspace. This answers a question implicit in Partington [P 80].