Robustness of orthogonal matching pursuit under restricted isometry property

Orthogonal matching pursuit(OMP)algorithm is an efcient method for the recovery of a sparse signal in compressed sensing,due to its ease implementation and low complexity.In this paper,the robustness of the OMP algorithm under the restricted isometry property(RIP) is presented.It is shown that δK+√KθK,11is sufcient for the OMP algorithm to recover exactly the support of arbitrary K-sparse signal if its nonzero components are large enough for both l2bounded and l∞bounded noises.     

On linear summation methods of Fourier series

Получены новые оценк иL-нормы тригонометр ических полиномов $$T_n (t) = \frac{{\lambda _0 }}{2} + \mathop \sum \limits_{k = 1}^n \lambda _k \cos kt$$ в терминах коэффицие нтовλ _k и их разностейΔλ _k=λ _k?λ _k?1: (1) $$\mathop \smallint \limits_{ - \pi }^\pi |T_n (t)|dt \leqq \frac{c}{n}\mathop \sum \limits_{k = 0}^n |\lambda _\kappa | + c\left\{ {x(n,\varphi )\mathop \sum \limits_{k = 0}^n \Delta \lambda _\kappa \mathop \sum \limits_{l = 0}^n \Delta \lambda _l \delta _{\kappa ,l} (\varphi )} \right\}^{{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} ,$$ где $$\kappa (n,\varphi ) = \mathop \smallint \limits_{1/n}^\pi [t^2 \varphi (t)]^{ - 1} dt, \delta _{k,1} (\varphi ) = \mathop \smallint \limits_0^\infty \varphi (t)\sin \left( {k + \frac{1}{2}} \right)t \sin \left( {l + \frac{1}{2}} \right)t dt,$$ a ?(t) — произвольная фун кция ≧0, для которой опр еделены соответствующие инт егралы. Из (1) следует, что методы $$\tau _n (f;t) = (N + 1)^{ - 1} \mathop \sum \limits_{k = 0}^{\rm N} S_{[2^{k^\varepsilon } ]} (f;t), n = [2^{N\varepsilon } ],$$ являются регулярным и для всех 0<ε≦1/2. ЗдесьS _m (f, x) частные суммы ряда Фу рье функцииf(x). В статье исследуется многомерный случай. П оказано, что метод суммирования (о бобщенный метод Рисса) с коэффиц иентами $$\lambda _{\kappa ,l} = (R^v - k^\alpha - l^\beta )^\delta R^{ - v\delta } (0 \leqq k^\alpha + l^\beta \leqq R^v ;\alpha \geqq 1,\beta \geqq 1,v< 0)$$ является регулярным, когда δ > 1.     

Existence results for quasilinear elliptic equations with multivalued nonlinear terms

In this paper we study the existence of solutions u ∈ \({{W}^{1,p}_{0}}\) (Ω) with △ _p u ∈ L ²(Ω) for the Dirichlet problem 1 $$ \left\{ \begin{array} [c]{l}-\triangle_{p}u\left( x\right) \in-\partial{\Phi}\left( u\left( x\right) \right) +G\left( x,u\left( x\right) \right) ,x\in{\Omega},\\ u\mid_{\partial{\Omega}}=0, \end{array} \right. $$ where Ω ? R ^N is a bounded open set with boundary ?Ω, △ _p stands for the p?Laplace differential operator, ?Φ denotes the subdifferential (in the sense of convex analysis) of a proper convex and lower semicontinuous function Φ and G : Ω × R → 2^R is a multivalued map. We prove two existence results: the first one deals with the case where the multivalued map u ? G(x, u) is upper semicontinuous with closed convex values and the second one deals with the case when u ? G(x, u) is lower semicontinuous with closed (not necessarily convex) values.     

Approximation of integrable functions by linear methods almost everywhere

It is shown that 2π periodic functions whose (r-1)-th derivatives have bounded variation (r > 0) can be approximated by de La Vallée-Poussin sums σ _n,m (an ?m =m (n) ?An,0 <a<A<1) at almost all points with a rate o(n^?r). For functions belonging to the class Lip (α, L) (0 <α < 1), any natural N, and a positive ?, we have almost everywhere $$|f(x) - \sigma _{n,m} (f;x)| \leqslant c(f,x)n^{ - \alpha } lnn \ldots ln_N^{1 + \varepsilon } n,$$ where \(ln_k x = \underbrace {ln \ldots ln x}_k(k = 1, 2, \ldots )\) . For any triangular method of summation T with bounded coefficients we construct functions belonging to Lip (α, L) (0 < α < 1) and such that almost everywhere, $$\mathop {\overline {\lim } }\limits_{n \to \infty } |f(x) - \tau _n (f;x)|n^a (ln n \ldots ln_N n)^{ - a} = \infty $$ where the τ_n(f; x) are the means of the method T.     

Nearly Quartic Mappings in β-Homogeneous F-Spaces

In this paper, we investigate the Hyers–Ulam stability of the following quartic equation $$\begin{array}{ll} {\sum\limits^{n}_{k=2}}\left({\sum\limits^{k}_{i_{1}=2}}{\sum\limits^{k+1}_{i_{2}=i_{1}+1}} \ldots {\sum\limits^{n}_{i_{n-k+1}=i_{n-k}+1}}\right)\\ \quad\times f \left({\sum\limits^{n}_{i=1,i \neq i_{1},\ldots,i_{n-k+1}}} x_{i}-{\sum\limits^{n-k+1}_{r=1}}x_{i_{r}}\right) + f \left({\sum\limits^{n}_{i=1}}x_{i}\right)\\ \quad-2^{n-2}{\sum\limits^{}_{1 \leq{i} \leq{j} \leq{n}}}(f(x_{i} + x_{j}){+f(x_{i} - x_{j})){+2^{n-5}(n - 2){\sum\limits^{n}_{i=1}}f(2x_{i})}} = \theta \end{array} $$ $({n \in \mathbb{N}, n \geq 3})$ in β-homogeneous F-spaces.     

Factorization of a convolution-type operator

Three convolution-type equations are considered in the space of entire functions with topology ofd uniform convergence: $$\begin{gathered} M{_{\mu}{_1}} [f] \equiv \smallint _C f(z + t)d\mu _1 = 0, \hfill \\ M{_\mu{_1}} [f] \equiv \smallint _C f(z + t)d\mu _2 = 0, \hfill \\ M_\mu [f] \equiv \smallint _C f(z + t)d\mu = 0 \hfill \\ \end{gathered}$$ with respective characteristic functions L₁(λ), L₂(λ), L(λ)=L₁(λ)· L₂(λ), suppμ ?c, suppμ ₁ ?c, suppμ ₂ ?c. The necessary and sufficient conditions are found that every solutionf(z) of the equation M_μ[f[ can be written as a sumf ₁(z) +f ₂(z), wheref ₁(z) is the solution of the equation \(M{_\mu{_1}} [f] = 0\) ,f ₂(z) is the solution of the equation \(M{_\mu{_2}} [f] = 0\) .     

ОцЕНкА (ε, δ)-ЁНтРОпИИ к лАссА цЕлых ФУНкцИИ В ИНтЕгРАльНОИ МЕтРИ кЕ

LetB _σ be the class of entire functions of exponential type σ, real valued and bounded in modulus by 1 in the real line. A setG of functions defined on the segment [-T-r, T+r], wherer is a fixed positive number, is called an (ε, δ)-net of the classB _σ on the segment [-т, т] if for any f?B _σ there existsg?G such that for anyx?[-T,T] $$\left| {f(x) - g(x)} \right| \leqq \frac{\varepsilon }{{2r}}\int\limits_{x - r}^{x + r} {\left| {f(t)} \right|dt + \delta .} $$ The main result consists in the following: For any positive σ, r, ε≦1, δ≦1 and sufficiently largeT we have $$H_{\varepsilon ,\delta } (B_\sigma ,T) \leqq \frac{{2\sigma T}}{\pi }\log \frac{{c(\sigma r)}}{{\max (\varepsilon ,\delta )}},$$ where c(σr) depends only on the product σr. The main tool of the proof of this inequality is the following estimate of the derivative of a polynomialP(x) with real coefficients: $$\left\| {P'(x)} \right\|_{L_p ( - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2},{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}) \leqq } c\left( {q + 1 + \sum\limits_{i = 1}^{n - q} {\frac{1}{{\left| {a_i } \right|^2 }}} } \right)\left\| {P(x} \right\|_{L_p ( - 1,1)} ,$$ whereq is the number of roots of the polynomialP(x) lying in the disk ¦z¦<1; a₁, ..., a_n?g are the other roots, с is an absolute constant, and 1≦p≦∞.     

A moment theorem for completely hyperexpansive operators

Given a family $ \{ A_m^x \} _{\mathop {m \in \mathbb{Z}_ + ^d }\limits_{x \in X} } $ (X is a non-empty set) of bounded linear operators between the complex inner product space $ \mathcal{D} $ and the complex Hilbert space ? we characterize the existence of completely hyperexpansive d-tuples T = (T ₁, … , T _d ) on ? such that A _m ^x = T ^m A ₀ ^x for all m ? ? ₊ ^d and x ? X.     

Logarithmically Improved Regularity Conditions for the 3D Navier–Stokes Equations

In this paper, we consider two new regularity criteria for the 3D Navier–Stokes equations involving partial components of the velocity in multiplier spaces. It is proved that if the horizontal velocity ? = (u ₁,u ₂,0) satisfies $$\int_{0}^{T} \frac{\|\tilde{u}\|_{\dot{X}_{r}}^{\frac{2}{1-r}}}{1+ln(e + \|u(t,.)\|_{\infty})}{\rm d}t < \infty, \quad r \in[0, 1),$$ or the horizontal gradient field satisfies $$\int_{0}^{T}\frac{\|\nabla_{h}\tilde{u}\|_{\dot{X}_{r}}^{\frac{2}{2-r}}}{1 + ln(e + \|u(t,.)\|_{\infty})}{\rm d}t < \infty, \quad r \in[0, 1],$$ then the local strong solution remains smooth on [0, T].     

On prime numbers of special kind on short intervals

Suppose that the Riemann hypothesis holds. Suppose that $$\psi _1 (x) = \mathop \sum \limits_{\begin{array}{*{20}c} {n \leqslant x} \\ {\{ (1/2)n^{1/c} \} < 1/2} \\ \end{array} } \Lambda (n)$$ where c is a real number, 1 < c ≤ 2. We prove that, for H>N ^1/2+10ε, ε > 0, the following asymptotic formula is valid: $$\psi _1 (N + H) - \psi _1 (N) = \frac{H}{2}\left( {1 + O\left( {\frac{1}{{N^\varepsilon }}} \right)} \right)$$ .     

A local mountain pass type result for a system of nonlinear Schr?dinger equations

We consider a singular perturbation problem for a system of nonlinear Schr?dinger equations: $$ \begin{array}{l} -\varepsilon^2\Delta v_1 +V_1(x)v_1 = \mu_1 v_1^3 + \beta v_1v_2^2 \quad {\rm in}\,\,{\bf R}^N, \\ -\varepsilon^2\Delta v_2 +V_2(x)v_2 = \mu_2 v_2^3 + \beta v_1^2v_2 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x) >0 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x)\in H^1({\bf R}^N), \end{array} \quad\quad\quad\quad\quad (*) $$ where N?=?2, 3, ?? ₁, ?? ₂, ?? > 0 and V ₁(x), V ₂(x): R ^N ?? (0, ??) are positive continuous functions. We consider the case where the interaction ?? > 0 is relatively small and we define for ${P\in{\bf R}^N}$ the least energy level m(P) for non-trivial vector solutions of the rescaled ??limit?? problem: $$ \begin{array}{l} -\Delta v_1 +V_1(P)v_1 = \mu_1 v_1^3 + \beta v_1v_2^2 \quad {\rm in}\,\,{\bf R}^N, \\ -\Delta v_2 +V_2(P)v_2 = \mu_2 v_2^3 + \beta v_1^2v_2 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x) >0 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x)\in H^1({\bf R}^N). \end{array} \quad\quad\quad\quad\quad\quad (**) $$ We assume that there exists an open bounded set ${\Lambda\subset{\bf R}^N}$ satisfying $$ {\mathop {\rm inf} _{P\in\Lambda} m(P)} < {\mathop {\rm inf}_{P\in\partial\Lambda} m(P)}. $$ We show that (*) possesses a family of non-trivial vector positive solutions ${\{(v_{1\varepsilon}(x), v_{2\varepsilon} (x))\}_{\varepsilon\in (0,\varepsilon_0]}}$ which concentrates??after extracting a subsequence ?? _n ?? 0??to a point ${P_0\in\Lambda}$ with ${m(P_0)={\rm inf}_{P\in\Lambda}m(P)}$ . Moreover (v _1?? (x), v _2?? (x)) converges to a least energy non-trivial vector solution of (**) after a suitable rescaling.     

Asymptotics for the minimization of a Ginzburg-Landau functional

LetΩ ? ?² be a smooth bounded simply connected domain. Consider the functional $$E_\varepsilon (u) = \frac{1}{2}\int\limits_\Omega {\left| {\nabla u} \right|^2 + \frac{1}{{4\varepsilon ^2 }}} \int\limits_\Omega {(|u|^2 - 1)^2 } $$ on the classH _g ¹ ={u εH ¹(Ω; ?);u=g on ?Ω} whereg:?Ω? → ? is a prescribed smooth map with ¦g¦=1 on ?Ω? and deg(g, ?Ω)=0. Let uu _ε be a minimizer for E_ε onH _g ¹ . We prove that u_ε → u₀ in \(C^{1,\alpha } (\bar \Omega )\) as ε → 0, where u₀ is identified. Moreover \(\left\| {u_\varepsilon - u_0 } \right\|_{L^\infty } \leqslant C\varepsilon ^2 \) .     

Алгебраические дроби Чебышева—Маркова на нескольких отрезках

The Chebyshev-Markov problem about real algebraic functions of the form $A_n (x) = \frac{{x^n + c_1 x^{n - 1} + ... + c_n }}{{\left( {\prod {_{i = 1}^{2n} } \left( {1 - a_{i,n} x} \right)} \right)^{1/2} }}$ deviated least from zero on a system of intervals $\left[ {b_1 ;b_2 } \right] \cup ... \cup \left[ {b_{2p - 1} ;b_{2p} } \right], - \infty< b_1 \leqslant b_2< ...< b_{2p - 1} \leqslant b_{2p}< + \infty $ is considered. The expression under the square root above is a real polynomial of degree less than 2n, which is positive on [b ₁;b _2p ]. The solution of this problem is given in a parametric form in terms of automorphic Schottky-Burside functions. Similar functions were first used by N. I. Akhyeser in the approximation theory.     

On the asymptotics of the Riesz-Bochner kernel

В работе рассматрива ется асимптотика в ме трике пространстваL _p (T ^N ),T ^N ={x∈R ^N , 0<x _i <2π} ядра Р исса-Бохнера $$\Theta ^s \left( {x, \lambda } \right) = \left( {2\pi } \right)^{ - N} \mathop \Sigma \limits_{\left| n \right|^2< \lambda } \left( {1 - \frac{{\left| n \right|^2 }}{\lambda }} \right)^s e^{inx} \left( {x \in T^N , s \geqq 0, \lambda \geqq 0} \right)$$ при λ→∞. Доказывается, что есл иN≧4,p≧2N/(N?1) иs>N((N?1)/2N?1/p), то для произвольной точкиx∈T ^N существует п остояннаяC=C _p (x, s) такая, что выполняется неравен ство $$\parallel \Theta ^s \left( {x - y, \lambda } \right) - \left( {2\pi } \right)^{ - {N \mathord{\left/ {\vphantom {N 2}} \right. \kern-\nulldelimiterspace} 2}} 2^s \Gamma \left( {s + 1} \right)\lambda ^{{N \mathord{\left/ {\vphantom {N 2}} \right. \kern-\nulldelimiterspace} 2}} J_{{N \mathord{\left/ {\vphantom {N {2 + s}}} \right. \kern-\nulldelimiterspace} {2 + s}}} {{\left( {\left| {x - y} \right|\sqrt \lambda } \right)} \mathord{\left/ {\vphantom {{\left( {\left| {x - y} \right|\sqrt \lambda } \right)} {\left( {\left| {x - y} \right|\sqrt \lambda } \right)^{{N \mathord{\left/ {\vphantom {N {2 + s}}} \right. \kern-\nulldelimiterspace} {2 + s}}} \parallel _{L_p \left( {T^N } \right)} \leqq }}} \right. \kern-\nulldelimiterspace} {\left( {\left| {x - y} \right|\sqrt \lambda } \right)^{{N \mathord{\left/ {\vphantom {N {2 + s}}} \right. \kern-\nulldelimiterspace} {2 + s}}} \parallel _{L_p \left( {T^N } \right)} \leqq }}$$ где нормаL _p (T ^N ) берется по пе ременнойy, а черезJ _v обозначена функция Б есселя первого рода порядкаv. СлучаиN=2 иN=3 рассматриваются отдельно.     

Bifurcation in a multicomponent system of nonlinear Schrödinger equations

We consider the system ${-\Delta{u}_{j} + a(x)u_{j} = \mu_{j}u^{3}_{j} + \beta \sum_{k \neq j} u^{2}_{k}u_{j}}$ , u _j > 0, j = 1, . . . , n, on a possibly unbounded domain ${\Omega \subset \mathbb{R}^{N}, N \leq 3}$ , with Dirichlet boundary conditions. The system appears in nonlinear optics and in the analysis of mixtures of Bose–Einstein condensates. We consider the self-focussing (attractive self-interaction) case ${\mu_{1}, \ldots, \mu_{n} > 0}$ and take ${\beta \in \mathbb{R}}$ as bifurcation parameter. There exists a branch of positive solutions with uj/uk being constant for all ${j, k \in \{1, \ldots, n\}}$ . The main results are concerned with the bifurcation of solutions from this branch. Using a hidden symmetry we are able to prove global bifurcation even when the linearization has even-dimensional kernel (which is always the case when n > 1 is odd).     

Schwache Lösungen des Frankl-Morawetz-Problems im ℝ3

In a bounded simple connected region G ? ?³ we consider the equation $$L\left[ u \right]: = k\left( z \right)\left( {u_{xx} + u_{yy} } \right) + u_{zz} + d\left( {x,y,z} \right)u = f\left( {x,y,z} \right)$$ where k(z)? 0 whenever z ? 0.G is surrounded forz≥0 by a smooth surface Γ₀ with S:=Γ₀ ? {(x,y,z)|=0} and forz<0 by the characteristic \(\Gamma _2 :---(x^2 + y^2 )^{{\textstyle{1 \over 2}}} + \int\limits_z^0 {(---k(t))^{{\textstyle{1 \over 2}}} dt = 0} \) and a smooth surface Γ₁ which intersect the planez=0 inS and where the outer normal n=(n_x, n_y, n_z) fulfills \(k(z)(n_x^2 + n_y^2 ) + n_z^2 |_{\Gamma _1 } > 0\) . Under conditions on Γ₁ and the coefficientsk(z), d(x,y,z) we prove the existence of weak solutions for the boundary value problemL[u]=f inG with \(u|_{\Gamma _0 \cup \Gamma _1 } = 0\) . The uniqueness of the classical solution for this problem was proved in [1].     

Support Recovery from Noisy Measurement via Orthogonal Multi-Matching Pursuit

In this paper, a new stopping rule is proposed for orthogonal multi-matching pursuit (OMMP). We show that, for $ℓ_2$ bounded noise case, OMMP with the new stopping rule can recover the true support of any $K$-sparse signal $x$ from noisy measurements $y = Φx + e$ in at most $K$ iterations, provided that all the nonzero components of $x$ and the elements of the matrix $Φ$ satisfy certain requirements. The proposed method can improve the existing result. In particular, for the noiseless case, OMMP can exactly recover any $K$-sparse signal under the same RIP condition.     

An extremal problem for algebraic polynomials in the symmetric discrete Gegenbauer-Sobolev space

We study discrete Sobolev spaces with symmetric inner product $$\left\langle {f,g} \right\rangle _\alpha = \int_{ - 1}^1 {f g d\mu _\alpha } + M[f(1)g(1) + f( - 1)g( - 1)] + K[f'(1)g'(1) + f'( - 1)g'( - 1)]$$ , where M ≥ 0, k ≥ 0, and $$d\mu _\alpha (x) = \frac{{\Gamma (2\alpha + 2)}}{{2^{2\alpha + 1} \Gamma ^2 (\alpha + 1)}}(1 - x^2 )^\alpha dx, \alpha > - 1$$ , is the Gegenbauer probability measure. We obtain the solution of the following extremal problem: Calculate $$\mathop {\inf }\limits_{a_0 ,a_1 ,...,a_{N - r} } \left\{ {\langle P_N^{(r)} ,P_N^{(r)} \rangle _\alpha ,1 \leqslant r \leqslant N - 1, P_N^{(r)} (x) = \sum\limits_{j = N - r + 1}^N {a_j^0 x^j } + \sum\limits_{j = 0}^{N - r} {a_j x^j } } \right\}$$ , where the a _j ⁰ , j = N ? r + 1, N ? r + 2, ..., N ? 1, N, a _N ⁰ > 0, are fixed numbers, and find the extremal polynomial.     

A Unified Framework for Linear Dimensionality Reduction in L1

For a family of interpolation norms \({\| \cdot \|_{1,2,s}}\) on \({\mathbb{R}^{n}}\), we provide a distribution over random matrices \({\Phi_s \in \mathbb{R}^{m \times n}}\) parametrized by sparsity level s such that for a fixed set X of K points in \({\mathbb{R}^{n}}\), if \({m \geq C s \log(K)}\) then with high probability, \({\frac{1}{2}\| \varvec{x} \|_{1,2,s} \leq \| \Phi_s (\varvec{x}) \|_1 \leq 2 \| \varvec{x} \|_{1,2,s}}\) for all \({\varvec{x} \in X}\). Several existing results in the literature roughly reduce to special cases of this result at different values of s: For s = n, \({\| \varvec{x} \|_{1,2,n}\equiv \| \varvec{x} \|_{1}}\) and we recover that dimension reducing linear maps can preserve the ?₁-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For s = 1, \({\| \varvec{x} \|_{1,2,1}\equiv \| \varvec{x} \|_{2}}\), and we recover an ?₂/?₁ variant of the Johnson–Lindenstrauss Lemma for Gaussian random matrices. Finally, if \({\varvec{x}}\) is s- sparse, then \({\| \varvec{x} \|_{1,2,s} = \| \varvec{x} \|_1}\) and we recover that s-sparse vectors in \({\ell_1^n}\) embed into \({\ell_1^{\mathcal{O}(s \log(n))}}\) via sparse random matrix constructions.     

On the Non-Commutative Neutrix Product of the Distributions x＋^λ and x^＋μ

Let f and g be distributions and let gn = （g ＊ δn）（x）, where δn （x） is a certain converging to the Dirac delta function. The non-commutative neutrix product fog of f and g to be the limit of the sequence {fgn }, provided its limit h exists in the sense that sequence is defined N-lim n-∞（f（x）g,, （x）, φ（x）〉 = （h（x）, φ（x）},for all functions p in 2. It is proved that （x^λ＋1n^px＋）0（x^μ＋1n^qx＋）=x＋^λμ1n^p＋qx＋,（x^λ-1n^qx-）=x-^λ＋μ1n^p＋qx-,for λ＋μ〈-1; λ,μ, λ＋μ≠-1,-2…and p,q=0,1,2……