Orthogonal almost locally minimal projections on ℓ 1 n

A projectionP on a Banach spaceX with ‖P‖≤λ₀ is called almost locally minimal if, for every α>0 small enough, the ballB(P,α) in the space of operatorsL(X) does not contain a projectionQ with ‖Q‖≤‖P‖(1–Dα²), whereD=D(λ₀) is a constant independent of ‖P‖. It is shown that, for everyp≥1 and every compact abelian groupG, every translation invariant projection onL _p(G) is almost locally minimal. Orthogonal projections on ℓ ₁ ⁿ are investigated with respect to some weaker local minimality properties. Participant in Workshop in Linear Analysis and Probability, Texas A&M University, College Station, Texas 1998. Partially supported by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

Cuts,Trees and ℓ<Subscript>1</Subscript>-Embeddings of Graphs*

Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into ₁ space. The main results are:1. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number. These are the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, algorithms are obtained which approximate the sparsest cut in such graphs to within a constant factor.2. A constant-distortion embedding of outerplanar graphs into the restricted class of ₁-metrics known as dominating tree metrics. A lower bound of (log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics is also presented. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low treewidth, and excludes the possibility of using them to explore the finer structure of ₁-embeddability.* A preliminary version of this work appeared in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 399–408. This work was done while the author was at the University of California, Berkeley. Supported in part by NSF grants CCR-9505448 and CCR-9820951.     

Biflatness of ℓ<Superscript>1</Superscript>-Semilattice Algebras

We show that if L is a semilattice then the ℓ¹-convolution algebra of L is biflat precisely when L is "uniformly locally finite". Our proof technique shows in passing that if this convolution algebra is biflat then it is isomorphic as a Banach algebra to the Banach space ℓ¹(L) equipped with pointwise multiplication. At the end we sketch how these techniques may be extended to prove an analogous characterisation of biflatness for Clifford semigroup algebras.     

Function spaces not containing ℓ<Subscript>1</Subscript>

For Ω bounded and open subset of andX a reflexive Banach space with 1-symmetric basis, the function spaceJF _X (Ω) is defined. This class of spaces includes the classical James function space. Every member of this class is separable and has non-separable dual. We provide a proof of topological nature thatJF _X (Ω) does not contain an isomorphic copy of ℓ₁. We also investigate the structure of these spaces and their duals.     

ℓ1-Rigid Graphs

An ₁-graph is a graph whose nodes can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the corresponding nodes. We show that many interesting graphs are ₁-rigid, i.e., that they admit an essentially unique such binary labeling.     

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.      

The Szlenk index and local ℓ<Subscript>1</Subscript>-indices

We introduce two new local ₁-indices of the same type as the Bourgain ₁-index; the ⁺₁-index and the ⁺₁-weakly null index. We show that the ⁺₁-weakly null index of a Banach space X is the same as the Szlenk index of X, provided X does not contain ₁. The ⁺₁-weakly null index has the same form as the Bourgain ₁-index: if it is countable it must take values for some <₁. The different ₁-indices are closely related and so knowing the Szlenk index of a Banach space helps us calculate its ₁-index, via the ⁺₁-weakly null index. We show that I(C(^{))=^1++1}.     

On discrete ℓ1-regularization

A real m × n matrix A and a vector y?∈?? ^m determine the discrete l ¹-regularization (DLR) problem 0.1 $$ \min \left\{\mbox{\,}|y-Ax|_1+\rho |x|_1:\,x\in\mathbb{R}^n \right\}, $$ where | · |₁ denotes the l ¹-norm of a vector and ρ?≥?0 is a nonnegative parameter. In this paper, we provide a detailed analysis of this problem which include a characterization of all solutions to (0.1), remarks about the geometry of the solution set and an effective iterative algorithm for numerical solution of (0.1). We are specially interested in the behavior of the solution of (0.1) as a function of ρ and in this regard, we prove in general the existence of critical values of ρ between which the l ¹-norm of any solution remains constant. These general remarks are significantly refined when A is a strictly totally positive (STP) matrix. The importance of STP matrices is well-established [5, 14]. Under this setting, the relationship between the number of nonzero coordinates of a distinguished solution of the DLR problem is precisely explained as a function of the regularization parameter for a certain class of vectors in ? ^m . Throughout our analysis of the DLR problem, we emphasize the importance of the dual maximum problem by demonstrating that any solution of it leads to a solution of the DLR problem, and vice versa.     

Convergence of the reweighted ℓ 1 minimization algorithm for ℓ 2–ℓ p minimization

The iteratively reweighted ? ₁ minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ? ₂–? _p minimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.     

Integral polynomials on Banach spaces not containing ℓ<Subscript>1</Subscript>

We give new characterizations of Banach spaces not containing ℓ₁ in terms of integral and p-dominated polynomials, extending to the polynomial setting a result of Cardassi and more recent results of Rosenthal.     

Congruences for ℓ-regular overpartition for ℓ ∈ {5, 6, 8}

Let A? _?(n) denote the number of overpartitions of a non-negative integer n with no part divisible by ?, where ? is a positive integer. In this paper, we prove infinite family of congruences for A? ₅(n) modulo 4, A? ₆(n) modulo 3, and A? ₈(n) modulo 4. In the process, we also prove some other congruences.     

On orthogonal linear ℓ1 approximation

Summary The problem is considered of orthogonal ₁ fitting of discrete data. Local best approximations are characterized and the question of the robustness of these solutions is considered. An algorithm for the problem is presented, along with numerical results of its application to some data sets.     

Remote Sensing via ℓ 1-Minimization

We consider the problem of detecting the locations of targets in the far field by sending probing signals from an antenna array and recording the reflected echoes. Drawing on key concepts from the area of compressive sensing, we use an ? ₁-based regularization approach to solve this, generally ill-posed, inverse scattering problem. As is common in compressive sensing, we exploit randomness, which in this context comes from choosing the antenna locations at random. With n antennas we obtain n ² measurements of a vector $x \in\mathbb{C}^{N}$ representing the target locations and reflectivities on a discretized grid. It is common to assume that the scene x is sparse due to a limited number of targets. Under a natural condition on the mesh size of the grid, we show that an s-sparse scene can be recovered via ? ₁-minimization with high probability if n ²≥Cslog²(N). The reconstruction is stable under noise and when passing from sparse to approximately sparse vectors. Our theoretical findings are confirmed by numerical simulations.     

Norming subspaces isomorphic to ℓ 1

Norming subspaces are studied widely in the duality theory of Banach spaces. These subspaces are applied to the Borel and Baire classifications of the inverse operators. The main result of this article asserts that the dual of a Banach space X contains a norming subspace isomorphic to l₁ provided that the following two conditions are satisfied: (1) X^* contains a subspace isomorphic to l₁; and (2) X^* contains a separable norming subspace.     

Geometric Characterizations for Subgroups of PU（1, n; C）

In this paper, we discuss non-elementary subgroups and discontinuous subgroups of PU(1,n; C), and give their geometric characterizations.     

Comparison of Some Distances Between Sums of ℓ n p Spaces

In this paper, we study the classical, modified, and weak Banach–Mazur distances between sums of _p ⁿ spaces. We explicitly calculate the classical and weak Banach–Mazur distances between sums of _p ⁿ spaces and establish bounds for the ratios of these distances.     

ℓ<Superscript>1</Superscript>-spreading models in mixed Tsirelson spacemodels in mixed Tsirelson space

Suppose that (F _n ) _n=1 ^∞ is a sequence of regular families of finite subsets of ℝ and (θ _n ) _n=1 ^∞ is a nonincreasing null sequence in (0,1). The mixed Tsirelson spaceT[(θ _n ,F _n ) _n=1 ^∞ ] is the completion ofc ₀₀ with respect to the implicitly defined norm , where the last supremum is taken over all sequences (E _i ) _i=1 ^k in [ℕ]^<∞ such that maxE _i<minE _i +1 and . Necessary and sufficient conditions are obtained for the existence of higher order ℓ¹-spreading models in every subspace generated by a subsequence of the unit vector basis ofT[(θ _n ,F _n ) _n=1 ^∞ ].     

The point of continuity property in Banach spaces not containing ℓ<Subscript>1</Subscript>

We obtain a local characterization of the point of continuity property for bounded subsets in Banach spaces not containing basic sequences equivalent to the standard basis of ℓ₁ and, as a consequence, we deduce that, in Banach spaces with a separable dual, every closed, bounded, convex and nonempty subset failing the point of continuity property contains a further subset which can be seen inside the set of Borel regular probability measures on the Cantor set in a weak-star dense way. Also, we characterize in terms of trees the point of continuity property of Banach spaces not containing ℓ₁, by proving that a Banach space not containing ℓ₁ satis- fies the point of continuity property if, and only if, every seminormalized weakly null tree has a boundedly complete branch.     

Spaces with Dual Order-Isomorphic to ℓ1

We establish that an ordered Banach space is order-isomorphic to c₀ if and only if it is a -Dedekind complete vector lattice and its norm dual is order-isomorphic to ₁.