Optimal noise suppression: A geometric nature of pseudoframes for subspaces

Pseudoframes for subspaces (PFFS) is a notion of frame-like expansions for a subspace in a separable Hilbert space [11]. The spanning nature of the sequences and in a PFFS (relative to the subspace ) is generally very different from that of a frame. Incidentally, a PFFS constitutes generally a nonorthogonal projections onto . The directions of the projection determine the geometric meanings and its applications of a PFFS. PFFS also provides a means for the construction of nonorthogonal projections that arises in various linear reconstruction problems. This article is aimed at elaborations on such geometrical properties, demonstration of natural needs of nonorthogonal projections in applications and how PFFS can be applied, particularly for optimal noise suppressions. In this specific application, we show that PFFS is not only natural and sufficient but also necessary for generating an optimal solution among the class of all linear and series-based methods.      

Pseudo Approximation Algorithms with Applications to Optimal Motion Planning

We introduce a technique for computing approximate solutions to optimization problems. If $X$ is the set of feasible solutions, the standard goal of approximation algorithms is to compute $x\in X$ that is an $\varepsilon$-approximate solution in the following sense: $$d(x) \leq (1+\varepsilon)\, d(x^*),$$ where $x^* \in X$ is an optimal solution, $d\colon\ X\rightarrow {\Bbb R}_{\geq 0}$ is the optimization function to be minimized, and $\varepsilon>0$ is an input parameter. Our approach is first to devise algorithms that compute pseudo $\varepsilon$-approximate solutions satisfying the bound $$d(x) \leq d(x_R^*) + \varepsilon R,$$ where $R>0$ is a new input parameter. Here $x^*_R$ denotes an optimal solution in the space $X_R$ of $R$-constrained feasible solutions. The parameter $R$ provides a stratification of $X$ in the sense that (1) $X_R \subseteq X_{R}$ for $R < R$ and (2) $X_R = X$ for $R$ sufficiently large. We first describe a highly efficient scheme for converting a pseudo $\varepsilon$-approximation algorithm into a true $\varepsilon$-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than $\varepsilon$-approximation algorithms. Another benefit is that our algorithm is automatically precision-sensitive. We apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in three dimensions, and (B) $d_1$-optimal motion for a rod moving amidst planar obstacles (1ORM). Previously, no polynomial time $\varepsilon$-approximation algorithm for (B) was known. For (A), our new solution is simpler than previous solutions and has an exponentially smaller complexity in terms of the input precision.     

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     

Regularity of Solution Maps of Differential Inclusions Under State Constraints

Consider a differential inclusion under state constraints

Mordell's exponential sum estimate revisited

The aim of this paper is to extend recent work of S. Konyagin and the author on Gauss sum estimates for large degree to the case of `sparse' polynomials. In this context we do obtain a nearly optimal result, improving on the works of Mordell and of Cochrane and Pinner. The result is optimal in terms of providing some power gain under conditions on the exponents in the polynomial that are best possible if we allow arbitrary coefficients. As in earlier work referred to above, our main combinatorial tool is a sum-product theorem. Here we need a version for product spaces for which the formulation is obviously not as simple as in the -case.

Again, the method applies more generally to provide nontrivial bounds on (possibly incomplete) exponential sums involving exponential functions. At the end of the paper, some applications of these are given to issues of uniform distribution for power generators in cryptography.

     

Elliptic reconstruction and a posteriori error estimates for fully discrete linear parabolic problems

We derive a posteriori error estimates for fully discrete approximations to solutions of linear parabolic equations. The space discretization uses finite element spaces that are allowed to change in time. Our main tool is an appropriate adaptation of the elliptic reconstruction technique, introduced by Makridakis and Nochetto. We derive novel a posteriori estimates for the norms of and the higher order spaces, and , with optimal orders of convergence.

     

Reduction of exterior differential systems with infinite dimensional symmetry groups

A symmetry-based method for constructing solutions to systems of differential equations founded on the reduction of exterior differential systems invariant under the action of an infinite dimensional pseudogroup is proposed. One can associate to any system of differential equations Δ=0 with a symmetry group an exterior differential system invariant under so that solutions of Δ=0 correspond to integral manifolds . The -invariant exterior differential system gives rise to a reduced system specified on a cross section to the pseudogroup orbits, and it is shown that solutions to Δ=0 can be reconstructed from integral manifolds by solving an equation of generalized Lie type for the jets of pseudogroup transformations. In particular, as opposed to the classical method of symmetry reduction, every solution to the system of differential equations can, under some mild regularity assumptions, be constructed by the present algorithm. AMS subject classification (2000)  58A15, 58A20, 58H05, 58J70     

On nonlocal calculation for inhomogeneous indefinite Neumann boundary value problems

This paper concerns with a family of inhomogeneous Neumann boundary value problems having indefinite nonlinearities which depend on a real parameter . We discuss the existence and the multiplicity of positive solutions with respect to . Developing the fibering method further, we can introduce a constructive concept of the calculation of certain nonlocal intervals , the so-called sufficient intervals of the existence. Then we are able to prove some new results on the existence and the multiplicity of positive solutions for .Received: 22 December 2003, Accepted: 29 January 2004, Published online: 16 July 2004Mathematics Subject Classification (2000): 35J70, 35J65, 47H17     

Minimal nodal solutions of the pure critical exponent problem on a symmetric domain

We establish existence of nodal solutions to the pure critical exponent problem in u = 0 on where a bounded smooth domain which is invariant under an orthogonal involution of We extend previous results for positive solutions due to Coron, Dancer, Ding, and Passaseo to existence and multiplicity results for solutions which change sign exactly once.Received: 4 April 2003, Accepted: 26 August 2003, Published online: 24 November 2003Mathematics Subject Classification (2000): 35J65, 35J20Research partially supported by PAPIIT, UNAM, under grant IN110902-3.     

Uniformly Elliptic PDEs with Bounded,Measurable Coefficients

Let $L[\,\cdot\,]Let be a nondivergent linear second-order uniformly elliptic partial differential operator defined on functions with domain Consider the question, "When is a function u a solution of on ?" The naive answer, "u is a solution of on if and for all " is clearly too limited. Indeed, if the coefficients of L are in then L can be rewritten in divergence form for which the notion of a "weak" solution can be applied. In this case there could be infinitely many functions that are "weak" but not classical solutions. More importantly, even if the coefficients of L are just bounded and measurable, the recent results of Krylov permit us to construct "solutions" of on and these "solutions" are generally no better than continuous; the "weak" solutions previously mentioned can be obtained by this construction, too. The preceding discussion provides us with an adequate extrinsic definition of solution (i.e., given a function u we either prove that it is or is not the result of such a construction) that has been used by several authors, but one that is not particularly satisfying or illuminating. Our major contribution in this paper is to show the following. I. There is an intrinsic definition of solution that is equivalent to the extrinsic one. II. Furthermore, the intrinsic definition is just the (now) well-known Crandall-Lions viscosity solution, modified in a natural way to accommodate measurable coefficients.     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.     

Isoperimetric Polygons of Maximum Width

The value is shown to be an upper bound on the width of any n-sided polygon with unit perimeter. This bound is reached when n is not a power of 2, and the corresponding optimal solutions are the regular polygons when n is odd and clipped regular Reuleaux polygons when n is even but not a power of 2. Using a global optimization algorithm, we show that the optimal width for the quadrilateral is with a precision of 10⁻⁴. We propose two mathematical programs to determine the maximum width when n=2 ^s with s≥3 and provide approximate, but near-optimal, solutions obtained by various heuristics and local optimization for n=8, 16, and 32. Work of the first author was supported by NSERC grant 239436-01, AFOSR FA9550-07-1-0302, and ExxonMobil. Work of the second author was supported by NSERC grant 239436-01.     

Existence and Stability Results for Renormalized Solutions to Noncoercive Nonlinear Elliptic Equations with Measure Data

In this paper we prove the existence of a renormalized solution to a class of nonlinear elliptic problems whose prototype is

Frames in spaces with finite rate of innovation

Signals with finite rate of innovation are those signals having finite degrees of freedom per unit of time that specify them. In this paper, we introduce a prototypical space modeling signals with finite rate of innovation, such as stream of (different) pulses found in GPS applications, cellular radio and ultra wide-band communication. In particular, the space is generated by a family of well-localized molecules of similar size located on a relatively separated set using coefficients, and hence is locally finitely generated. Moreover that space includes finitely generated shift-invariant spaces, spaces of non-uniform splines, and the twisted shift-invariant space in Gabor (Wilson) system as its special cases. Use the well-localization property of the generator , we show that if the generator is a frame for the space and has polynomial (sub-exponential) decay, then its canonical dual (tight) frame has the same polynomial (sub-exponential) decay. We apply the above result about the canonical dual frame to the study of the Banach frame property of the generator for the space with , and of the polynomial (sub-exponential) decay property of the mask associated with a refinable function that has polynomial (sub-exponential) decay.      

Isomorphism problems and groups of automorphisms for generalized Weyl algebras

We present solutions to isomorphism problems for various generalized Weyl algebras, including deformations of type-A Kleinian singularities and the algebras similar to introduced by S. P. Smith. For the former, we generalize results of Dixmier on the first Weyl algebra and the minimal primitive factors of by finding sets of generators for the group of automorphisms.

     

Singular perturbation method for inhomogeneous nonlinear free boundary problems

In this paper, we study solutions of one phase inhomogeneous singular perturbation problems of the type: $ F(D^2u,x)=\beta _{\varepsilon }(u) + f_{\varepsilon }(x) $ and $ \Delta _{p}u=\beta _{\varepsilon }(u) + f_{\varepsilon }(x)$ , where $\beta _{\varepsilon }$ approaches Dirac $\delta _{0}$ as $\varepsilon \rightarrow 0$ and $f_{\varepsilon }$ has a uniform control in $L^{q}, q>N.$ Uniform local Lipschitz regularity is obtained for these solutions. The existence theory for variational (minimizers) and non variational (least supersolutions) solutions for these problems is developed. Uniform linear growth rate with respect to the distance from the $\varepsilon -$ level surfaces are established for these variational and nonvaritional solutions. Finally, letting $\varepsilon \rightarrow 0$ basic properties such as local Lipschitz regularity and non-degeneracy property are proven for the limit and a Hausdorff measure estimate for its free boundary is obtained.     

Boundary Sensitivities for Diffusion Processes in Time Dependent Domains

We study the sensitivity, with respect to a time dependent domain of expectations of functionals of a diffusion process stopped at the exit from or normally reflected at the boundary of We establish a differentiability result and give an explicit expression for the gradient that allows the gradient to be computed by Monte Carlo methods. Applications to optimal stopping problems and pricing of American options, to singular stochastic control and others are discussed.     

A local search using solution fragments for the 2-machine bicriteria scheduling problem

In this work, we introduce a local search strategy for combinatorial optimization problems which explores neighborhoods obtained using fragments of current solutions. We apply the approach to the well-known -hard 2-machine bicriteria flowshop scheduling problem. Computational experiments using benchmark data show the approach to be effective when compared to other algorithms available for the problem.     

Multiple positive solutions for time scale boundary value problems on infinite intervals

The study of dynamic equations on time scales is an area of mathematics. It has been created in order to unify the study of differential and difference equations. In this paper, we consider the time-scale boundary value problems

A chain rule in $L^{1}\left({\operatorname*{div};\Omega}\right)$ and its applications to lower semicontinuity

A chain rule in the space is obtained under weak regularity conditions. This chain rule has important applications in the study of lower semicontinuity problems for general functionals of the form with respect to strong convergence in . Classical results of Serrin and of De Giorgi, Buttazzo and Dal Maso are extended and generalized.Received: 1 June 2002, Accepted: 7 January 2003, Published online: 6 June 2003