Primal and dual alternating direction algorithms for ℓ 1-ℓ 1-norm minimization problems in compressive sensing

In this paper, we propose, analyze and test primal and dual versions of the alternating direction algorithm for the sparse signal reconstruction from its major noise contained observation data. The algorithm minimizes a convex non-smooth function consisting of the sum of ? ₁-norm regularization term and ? ₁-norm data fidelity term. We minimize the corresponding augmented Lagrangian function alternatively from either primal or dual forms. Both of the resulting subproblems admit explicit solutions either by using a one-dimensional shrinkage or by an efficient Euclidean projection. The algorithm is easily implementable and it requires only two matrix-vector multiplications per-iteration. The global convergence of the proposed algorithm is established under some technical conditions. The extensions to the non-negative signal recovery problem and the weighted regularization minimization problem are also discussed and tested. Numerical results illustrate that the proposed algorithm performs better than the state-of-the-art algorithm YALL1.     

ℓ-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.      

Three-Dimensional ℓ-Algebras

The family of all three-dimensional almost f-algebras, d-algebras, and f-algebras is constructed. It is shown that it contains all three-dimensional directly indecomposable ?-algebras. Also, a list of representatives of (algebraic) isomorphism classes of all three-dimensional algebras that can be ordered as an almost f-algebra, a d-algebra, or an f-algebra is given.     

Lamron ℓ-groups

The article introduces a new class of lattice-ordered groups. An ?-group G is lamron if Min(G)^?1 is a Hausdorff topological space, where Min(G)^?1 is the space of all minimal prime subgroups of G endowed with the inverse topology. It will be evident that lamron ?-groups are related to ?-groups with stranded primes. In particular, it is shown that for a W-object (G,u), if every value of u contains a unique minimal prime subgroup, then G is a lamron ?-group; such a W-object will be said to have W-stranded primes. A diverse set of examples will be provided in order to distinguish between the notions of lamron, stranded primes, W-stranded primes, complemented, and weakly complemented ?-groups.     

Feebly projectable ℓ-groups

In the article [17], we introduced and investigated feebly and flatly projectable frames. In this article, we apply these two properties to lattice-ordered groups. An example is constructed to illustrate that the two properties are distinct, which solves a question from [17]. We also investigate these properties with respect to archimedean ℓ-groups with weak order unit, as well as commutative semiprime f-rings.     

Clean unital ℓ-groups

A ring with identity is said to be clean if every element can be written as a sum of a unit and an idempotent. The study of clean rings has been at the forefront of ring theory over the past decade. The theory of partially-ordered groups has a nice and long history and since there are several ways of relating a ring to a (unital) partially-ordered group it became apparent that there ought to be a notion of a clean partially-ordered group. In this article we define a clean unital lattice-ordered group; we state and prove a theorem which characterizes clean unital ?-groups. We mention the relationship of clean unital ?-groups to algebraic K-theory. In the last section of the article we generalize the notion of clean to the non-unital context and investigate this concept within the framework of W-objects, that is, archimedean ?-groups with distinguished weak order unit.     

ℓ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.     

ε-solutions in vector minimization problems

This paper presents some properties of -solutions for vector minimization problems where the function to be optimized takes its values in the Euclidean space ^p . The results obtained generalize the classical ones for exact Pareto solutions.     

Maximal ℓ-Frattini quotients of ℓ-Poincaré duality groups of dimension 2

Any morphism of profinite groups has maximal ℓ-Frattini quotients

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.     

Decomposition of ℓ-group-valued measures

We deal with decomposition theorems for modular measures µ: L → G defined on a D-lattice with values in a Dedekind complete ?-group. Using the celebrated band decomposition theorem of Riesz in Dedekind complete ?-groups, several decomposition theorems including the Lebesgue decomposition theorem, the Hewitt-Yosida decomposition theorem and the Alexandroff decomposition theorem are derived. Our main result—also based on the band decomposition theorem of Riesz—is the Hammer-Sobczyk decomposition for ?-group-valued modular measures on D-lattices. Recall that D-lattices (or equivalently lattice ordered effect algebras) are a common generalization of orthomodular lattices and of MV-algebras, and therefore of Boolean algebras. If L is an MV-algebra, in particular if L is a Boolean algebra, then the modular measures on L are exactly the finitely additive measures in the usual sense, and thus our results contain results for finitely additive G-valued measures defined on Boolean algebras.     

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.     

Pure ℓ-Ideals in Lattice-Ordered Rings#

An ?-ideal I of a commutative lattice-ordered ring R with positive identity element is called a pure ?-ideal if R  =  I  + ?( x ) for each x  ∈  I , where ?(x) is the ?-annihilator of x in R . In this article, we give some results on pure ?-ideals and study the ?-ideal structure of a commutative lattice-ordered ring with positive identity element by using pure ?-ideals.     

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.     

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.