Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms

Finding a sparse approximation of a signal from an arbitrary dictionary is a very useful tool to solve many problems in signal processing. Several algorithms, such as Basis Pursuit (BP) and Matching Pursuits (MP, also known as greedy algorithms), have been introduced to compute sparse approximations of signals, but such algorithms a priori only provide sub-optimal solutions. In general, it is difficult to estimate how close a computed solution is from the optimal one. In a series of recent results, several authors have shown that both BP and MP can successfully recover a sparse representation of a signal provided that it is sparse enough, that is to say if its support (which indicates where are located the nonzero coefficients) is of sufficiently small size. In this paper we define identifiable structures that support signals that can be recovered exactly by minimization (Basis Pursuit) and greedy algorithms. In other words, if the support of a representation belongs to an identifiable structure, then the representation will be recovered by BP and MP. In addition, we obtain that if the output of an arbitrary decomposition algorithm is supported on an identifiable structure, then one can be sure that the representation is optimal within the class of signals supported by the structure. As an application of the theoretical results, we give a detailed study of a family of multichannel dictionaries with a special structure (corresponding to the representation problem ) often used in, e.g., under-determined source sepa-ration problems or in multichannel signal processing. An identifiable structure for such dictionaries is defined using a generalization of Tropp’s Babel function which combines the coherence of the mixing matrix with that of the time-domain dictionary , and we obtain explicit structure conditions which ensure that both minimization and a multi-channel variant of Matching Pursuit can recover structured multichannel representations. The multichannel Matching Pursuit algorithm is described in detail and we conclude with a discussion of some implications of our results in terms of blind source separation based on sparse decompositions. Communicated by Yuesheng Xu     

Global error bounds for the extended vertical LCP

A new necessary and sufficient condition for the row -property is given. By using this new condition and a special row rearrangement, we provide two global error bounds for the extended vertical linear complementarity problem under the row -property, which extend the error bounds given in Chen and Xiang (Math. Program. 106:513–525, 2006) and Mathias and Pang (Linear Algebra Appl. 132:123–136, 1990) for the P-matrix linear complementarity problem, respectively. We show that one of the new error bounds is sharper than the other, and it can be computed easily for some special class of the row -property block matrix. Numerical examples are given to illustrate the error bounds. The work was in part supported by a Grant-in-Aid from Japan Society for the Promotion of Science, and the National Natural Science Foundation of China (10671010).     

The Gold Partition Conjecture

We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample.     

From light tails to heavy tails through multiplier

Let X and Y be two independent nonnegative random variables, of which X has a distribution belonging to the class or for some γ ≥ 0 and Y is unbounded. We study how their product XY inherits the tail behavior of X. Under some mild technical assumptions we prove that the distribution of XY belongs to the class or accordingly. Hence, the multiplier Y builds a bridge between light tails and heavy tails.      

Generalized Continuous Posets and a New Cartesian Closed Category

With every subset selection for posets, there is associated a certain ideal completion . As shown by Erné, such completions help to extend classical results on domains and similar structures in the absence of the required joins. Some results about –predistributive or –precontinuous posets and –continuous functions are summarized and supplemented. In particular, several central results on function spaces in domain theory are extended to the setting of productive closed subset selections. The category FSBP, in which objects are finitely separated and upper bounded posets and arrows are continuous functions between them, is shown to be cartesian closed. This research is supported by the National Natural Science Foundation of China, 10471035.     

Two-parameter p, q-variation Paths and Integrations of Local Times

In this paper, we prove two main results. The first one is to give a new condition for the existence of two-parameter -variation path integrals. Our condition of locally bounded -variation is more natural and easy to verify than those of Young. This result can be easily generalized to multi-parameter case. The second result is to define the integral of local time pathwise and then give generalized It’s formula when is only of bounded -variation in . In the case that is of locally bounded variation in , the integral is the Lebesgue–Stieltjes integral and was used by Elworthy, Truman and Zhao. When is of only locally -variation, where , , and , the integral is a two-parameter Young integral of -variation rather than a Lebesgue–Stieltjes integral. In the special case that is independent of , we give a new condition for Meyer's formula and is defined pathwise as a Young integral. For this we prove the local time is of -variation in for each , for each almost surely (-variation in the sense of Lyons and Young, i.e. ).     

Boundary Limits for Bounded Quasiregular Mappings

In this paper we establish results on the existence of nontangential limits for weighted -harmonic functions in the weighted Sobolev space , for some q>1 and w in the Muckenhoupt A _q class, where is the unit ball in . These results generalize the ones in Sect. 3 of Koskela et al., Trans. Am. Math. Soc. 348(2), 755–766, 1996, where the weight was identically equal to one. Weighted -harmonic functions are weak solutions of the partial differential equation

Universality of Coproducts in Categories of Lax Algebras

Categories of lax -algebras are shown to have pullback-stable coproducts if preserves inverse images. The general result not only gives a common proof of this property in many topological categories but also shows that important topological categories, like the category of uniform spaces, are not presentable as a category of lax -algebras, with preserving inverse images. Moreover, we show that any such category of -algebras has a concrete, coproduct preserving functor into the category of topological spaces.     

Boundedly UC Spaces and Topologies on Function Spaces

A new interesting topology on graphs of partial maps is introduced. This topology can be considered as a natural extension to a non locally compact setting of former topologies defined by P. Brandi, R. Ceppitelli and K. Back, having applications in mathematical economics, differential equations and in the convergence of dynamic programming models. New characterizations of boundedly Atsuji spaces are given by the coincidence of and the topology τ _ucb of uniform convergence on bounded sets on C(X,Y) and by topological properties of .      

Dirichlet Problem at Infinity for $\mathcal A$-Harmonic Functions

We study the Dirichlet problem at infinity for -harmonic functions on a Cartan–Hadamard manifold M and give a sufficient condition for a point at infinity x ₀∈M(∞) to be -regular. This condition is local in the sense that it only involves sectional curvatures of M in a set U∩M, where U is an arbitrary neighborhood of x ₀ in the cone topology. The results apply to the Laplacian and p-Laplacian, 1<p<∞, as special cases.      

Quasi-regular Dirichlet Forms and L^p-resolvents on Measurable Spaces

We prove that for any semi-Dirichlet form on a measurable Lusin space E there exists a Lusin topology with the given -algebra as the Borel -algebra so that becomes quasi-regular. However one has to enlarge E by a zero set. More generally a corresponding result for arbitrary -resolvents is proven.     

Meromorphic approximation theorem in a Stein space

We prove the meromorphic version of the Weil–Oka approximation theorem in a reduced Stein space X and give some characterizations of meromorphically -convex open sets of X. As an application we prove that for every meromorphically -convex open set D of a reduced Stein space X with no isolated points there exists a family of holomorphic functions on X such that the normality domain of coincides with D. Mathematics Subject Classification (2000)  32E10, 32C15, 32E30, 32A19     

Coherence for Product Monoids and their Actions

Let and be two monoids (algebras) in a monoidal category . Further let be a distributive law in the sense of [J. Beck, Lect. Notes Math., 80:119–140, 1969]; naturally yields a monoid . Consider a word in the symbols , , and . The first coherence theorem proved in this paper asserts that all morphisms coincide in , provided they arise as composites of morphisms which are -products of ’s ‘canonical’ structure morphisms, and of , , , , , , , and . Assume now that an object is endowed with both an -object structure , and an -object structure . Further assume that these two structures are compatible, in the sense that they naturally yield an -object . Let be a word in , , , and , which contains a single instance of , in the rightmost position. The second coherence theorem states that all morphisms coincide in , provided they arise as composites of morphisms which are -products of ’s ‘canonical’ structure morphisms, and of , , , , , , , , , and .     

Weak Barriers in Nonlinear Potential Theory

We characterize regular boundary points for p-harmonic functions using weak barriers. We use this to obtain some consequences on boundary regularity. The results also hold for -harmonic functions under the usual assumptions on , and for Cheeger p-harmonic functions in metric spaces.      

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

Linear Codes over \mathbb{F}_{q}[u]/(u^s) with Respect to the Rosenbloom–Tsfasman Metric

We investigate the structure of codes over rings with respect to the Rosenbloom-Tsfasman (RT) metric. We define a standard form generator matrix and show how we can determine the minimum distance of a code by taking advantage of its standard form. We define MDR (maximum distance rank) codes with respect to this metric and give the weights of the codewords of an MDR code. We explore the structure of cyclic codes over and show that all cyclic codes over rings are MDR. We propose a decoding algorithm for linear codes over these rings with respect to the RT metric. AMS Classification: 94B05, 94B60     

An algorithm for matching point sets using the l_1 norm

The problem is considered of matching two sets of points in , by translation and rotation. There are many applications, for example in geodesy, computer vision and in the assessment of manufactured parts. When the matching criterion is least squares, there is a well known solution process based on the singular value decomposition of an matrix. Here we consider the use of the norm, which may be more appropriate than least squares in the context of wild points in the data. An algorithm is developed, and is illustrated by some examples for the case .     

Inverse Conductivity Problem on Riemann Surfaces

An electrical potential U on a bordered Riemann surface X with conductivity function σ>0 satisfies equation d(σ d ^c U)=0. The problem of effective reconstruction of σ from electrical currents measurements (Dirichlet-to-Neumann mapping) on the boundary: U| _bX ↦ σ d ^c U| _bX is studied. We extend to the case of Riemann surfaces the reconstruction scheme given, firstly, by R. Novikov (Funkc. Anal. Ego Priloz. 22:11–22, 2008) for simply connected X. We apply for this new kernels for on the affine algebraic Riemann surfaces constructed in Henkin (, 2008).      

On Attractors for Multivalued Semigroups Defined by Generalized Semiflows

In this paper we extend results from Semigroup Theory on existence and characterization of attractors in order to include multivalued semigroups T(t) defined by generalized semiflows . In particular we show that, if is continuous, possesses a Lyapunov function, and has a global attractor which is maximal compact invariant, then  =  W ^u (Z()), where Z() is the stationary solutions set and W ^u (Z()) is the unstable set of Z(). We introduce the -attractor concept which does not enjoy any uniformity on time of attraction and we prove, under suitable conditions, that the global -attractor is the set of asymptotic states described by Z(). Jacson Simsen is supported by CAPES-Brazil.     

Semi-finite forms of bilateral basic hypergeometric series

We show that several classical bilateral summation and transformation formulas have semi-finite forms. We obtain these semi-finite forms from unilateral summation and transformation formulas. Our method can be applied to derive Ramanujan's summation, Bailey's transformations, and Bailey's summation.