Linear Transport Equations with μ-Monotone Coefficients

We introduce the concept of a μ-monotone function. It allows us to extend the existing theory for Filippov solutions to ODE, linear transport equations, and conservation laws for a wider range of transport velocities (A₁,…,A_d) and fluxes (f₁,…,f_d).     

Approximation of Functions of Few Variables in?High?Dimensions

Let f be a continuous function defined on Ω:=[0,1] ^N which depends on only ℓ coordinate variables, f(x₁,?,x_N)=g(x_i1,?,x_il)f(x_{1},\ldots,x_{N})=g(x_{i_{1}},\ldots,x_{i_{\ell}}). We assume that we are given m and are allowed to ask for the values of f at m points in Ω. If g is in Lip1 and the coordinates i ₁,…,i _ℓ are known to us, then by asking for the values of f at m=L ^ℓ uniformly spaced points, we could recover f to the accuracy |g|_Lip1 L ⁻¹ in the norm of C(Ω). This paper studies whether we can obtain similar results when the coordinates i ₁,…,i _ℓ are not known to us. A prototypical result of this paper is that by asking for C(ℓ)L ^ℓ (log ₂ N) adaptively chosen point values of f, we can recover f in the uniform norm to accuracy |g|_Lip1 L ⁻¹ when g∈Lip1. Similar results are proven for more general smoothness conditions on g. Results are also proven under the assumption that f can be approximated to some tolerance ε (which is not known) by functions of ℓ variables.     

Greedy wavelet projections are bounded on BV

Let be the space of functions of bounded variation on with . Let , , be a wavelet system of compactly supported functions normalized in , i.e., , . Each has a unique wavelet expansion with convergence in . If is the set of indicies for which are largest (with ties handled in an arbitrary way), then is called a greedy approximation to . It is shown that with a constant independent of . This answers in the affirmative a conjecture of Meyer (2001).

     

Instance-optimality in probability with an -minimization decoder

Let Φ(ω), ωΩ, be a family of n×N random matrices whose entries _i,j are independent realizations of a symmetric, real random variable η with expectation and variance . Such matrices are used in compressed sensing to encode a vector by y=Φx. The information y holds about x is extracted by using a decoder . The most prominent decoder is the ℓ₁-minimization decoder Δ which gives for a given the element which has minimal ℓ₁-norm among all with Φz=y. This paper is interested in properties of the random family Φ(ω) which guarantee that the vector will with high probability approximate x in to an accuracy comparable with the best k-term error of approximation in for the range kan/log₂(N/n). This means that for the above range of k, for each signal , the vector satisfies

with high probability on the draw of Φ. Here, Σ_k consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math., in press] who showed this property when η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where η is the Bernoulli random variable which takes the values with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005) 491–523].     

Best Basis Selection for Approximation in L p

We study the approximation of a function class F in L _p by choosing first a basis B and then using n -term approximation with the elements of B . Into the competition for best bases we enter all greedy (i.e., democratic and unconditional [20]) bases for L _p . We show that if the function class F is well-oriented with respect to a particular basis B then, in a certain sense, this basis is the best choice for this type of approximation. Our results extend the recent results of Donoho [9] from L ₂ to L _p , p\neq 2 .     

Quadrature formula for computed tomography

We give a bivariate analog of the Micchelli–Rivlin quadrature for computing the integral of a function over the unit disk using its Radon projections.