Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

In this paper, we improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. (1) In compressed sensing, we show that if the m×n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable ? ₁ minimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m)+1)). (2) In the very general sensing model introduced in Candès and Plan (IEEE Trans. Inf. Theory 57(11):7235–7254, 2011) and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log² n)) nonzero entries. (3) Finally, we prove that one can recover an n×n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(nlog² n)); again, this holds when there is a positive fraction of corrupted samples.     

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.     

The $$ \ell _1 $$-Analysis in Phase Retrieval with Redundant Dictionary

This article presents new results concerning the recovery of a signal from the magnitude only measurements where the signal is not sparse in an orthonormal basis but in a redundant dictionary, which we call it phase retrieval with redundant dictionary for short. To solve this phaseless problem, we analyze the \( \ell _1 \)-analysis model. Firstly we investigate the noiseless case with presenting a null space property of the measurement matrix under which the \( \ell _1 \)-analysis model provides an exact recovery. Secondly we introduce a new property (S-DRIP) of the measurement matrix. By solving the \( \ell _1 \)-analysis model, we prove that this property can guarantee a stable recovery of real signals that are nearly sparse in overcomplete dictionaries.     

Seifert manifolds and (1, 1)-knots

The aim of this paper is to investigate the relations between Seifert manifolds and (1, 1)-knots. In particular, we prove that each orientable Seifert manifold with invariants

$\{ Oo,0| - 1;\underbrace {(p,q),...,(p,q)}_{n times},(l,l - 1)\} $

has the fundamental group cyclically presented by G _n ((x ₁ ^q ...x _n ^{q l} x _n ^?p ) and, moreover, it is the n-fold strongly-cyclic covering of the lens space L(|nlq ? p|, q) which is branched over the (1, 1)-knot K(q, q(nl ? 2), p ? 2q, p ? q) if p ≥ 2q and over the (1, 1)-knot K(p? q, 2q ? p, q(nl ? 2), p ? q) if p< 2q.

     

Polyboxes,Cube Tilings and Rigidity

A non-empty subset A of X=X ₁×???×X _d is a (proper) box if A=A ₁×???×A _d and A _i ?X _i for each i. Suppose that for each pair of boxes A, B and each i, one can only know which of the three states takes place: A _i =B _i , A _i =X _i ?B _i , A _i ?{B _i ,X _i ?B _i }. Let F and G be two systems of disjoint boxes. Can one decide whether ∪F=∪G? In general, the answer is ‘no’, but as is shown in the paper, it is ‘yes’ if both systems consist of pairwise dichotomous boxes. (Boxes A, B are dichotomous if there is i such that A _i =X _i ?B _i .) Several criteria that enable to compare such systems are collected. The paper includes also rigidity results, which say what assumptions have to be imposed on F to ensure that ∪F=∪G implies F=G. As an application, the rigidity conjecture for 2-extremal cube tilings of Lagarias and Shor is verified.     

Construction of Carleman formulas by using mixed problems with parameter-dependent boundary conditions

Let D be an open connected subset of the complex plane C with sufficiently smooth boundary ?D. Perturbing the Cauchy problem for the Cauchy–Riemann system ??u = f in D with boundary data on a closed subset S ? ?D, we obtain a family of mixed problems of the Zaremba-type for the Laplace equation depending on a small parameter ε ∈ (0, 1] in the boundary condition. Despite the fact that the mixed problems include noncoercive boundary conditions on ?D\S, each of them has a unique solution in some appropriate Hilbert space H ⁺(D) densely embedded in the Lebesgue space L ₂(?D) and the Sobolev–Slobodetski? space H ^1/2?δ(D) for every δ > 0. The corresponding family of the solutions {u _ε} converges to a solution to the Cauchy problem in H ⁺(D) (if the latter exists). Moreover, the existence of a solution to the Cauchy problem in H ⁺(D) is equivalent to boundedness of the family {u _ε} in this space. Thus, we propose solvability conditions for the Cauchy problem and an effective method of constructing a solution in the form of Carleman-type formulas.     

Integral averaging technique for oscillation of damped half-linear oscillators

This paper is concerned with the oscillatory behavior of the damped half-linear oscillator (a(t)?_p(x′))′ + b(t)?_p(x′) + c(t)?_p(x) = 0, where ?p(x) = |x|^p?1 sgn x for x ∈ ? and p > 1. A sufficient condition is established for oscillation of all nontrivial solutions of the damped half-linear oscillator under the integral averaging conditions. The main result can be given by using a generalized Young’s inequality and the Riccati type technique. Some examples are included to illustrate the result. Especially, an example which asserts that all nontrivial solutions are oscillatory if and only if p ≠ 2 is presented.     

Criterion for the Solvability of the Weighted Cauchy Problem for an Abstract Euler–Poisson–Darboux Equation

In a Banach space E, we consider the abstract Euler–Poisson–Darboux equation u″(t) + kt^?1u′(t) = Au(t) on the half-line. (Here k ∈ ? is a parameter, and A is a closed linear operator with dense domain on E.) We obtain a necessary and sufficient condition for the solvability of the Cauchy problem u(0) = 0, lim _t→0+t ^k u′(t) = u₁, k < 0, for this equation. The condition is stated in terms of an estimate for the norms of the fractional power of the resolvent of A and its derivatives. We introduce the operator Bessel function with negative index and study its properties.     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

Semialgebraic sets and the Łojasiewicz-Siciak condition

The paper contains a full geometric characterization of compact semialgebraic sets in C satisfying the ?ojasiewicz-Siciak condition. The ?ojasiewicz-Siciak condition is a certain estimate for the Siciak extremal function. In a previous paper, we gave a sufficient criterion for a compact, connected, and semialgebraic set in C to satisfy this condition. In the present paper, we remove completely the connectedness assumption and prove that the aforementioned sufficient condition is also necessary. Moreover, we obtain some new results concerning the ?ojasiewicz-Siciak condition in C^N. For example, we prove that if K₁,...,K_p are compact, nonpluripolar, and pairwise disjoint subsets of C^N, each satisfying the ?ojasiewicz-Siciak condition, and K:= K₁?· · ·?K_p is polynomially convex, then K satisfies this condition as well.     

Approximation of Gaussian Random Fields: General Results and Optimal Wavelet Representation of the Lévy Fractional Motion

We investigate the approximation rate for certain centered Gaussian fields by a general approach. Upper estimates are proved in the context of so–called Hölder operators and lower estimates follow from the eigenvalue behavior of some related self–adjoint integral operator in a suitable L ₂(μ)–space. In particular, we determine the approximation rate for the Lévy fractional Brownian motion X _H with Hurst parameter H∈(0,1), indexed by a self–similar set T?? ^N of Hausdorff dimension D. This rate turns out to be of order n ^?H/D (log?n)^1/2. In the case T=[0,1] ^N we present a concrete wavelet representation of X _H leading to an approximation of X _H with the optimal rate n ^?H/N (log?n)^1/2.     

Some <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Rigidity Results for Complete Manifolds with Harmonic Curvature

Let (M ⁿ , g)(n ≥ 3) be an n-dimensional complete Riemannian manifold with harmonic curvature and positive Yamabe constant. Denote by R and R m? the scalar curvature and the trace-free Riemannian curvature tensor of M, respectively. The main result of this paper states that R m? goes to zero uniformly at infinity if for \(p\geq \frac n2\), the L ^p -norm of R m? is finite. Moreover, If R is positive, then (M ⁿ , g) is compact. As applications, we prove that (M ⁿ , g) is isometric to a spherical space form if for \(p\geq \frac n2\), R is positive and the L ^p -norm of R m? is pinched in [0, C ₁), where C ₁ is an explicit positive constant depending only on n, p, R and the Yamabe constant. We give an isolation theorem of the trace-free Ricci curvature tensor of compact locally conformally flat Riemannian n-manifolds with constant positive scalar curvature, which extends Theorem 1 of Hebey and M. Vaugon (J. Geom. Anal. 6, 531–553, 1996). This result is sharp, and we can precisely characterize the case of equality. In particular, when n = 4, we recover results by Gursky (Indiana Univ. Math. J. 43, 747–774, 1994; Ann. Math. 148, 315–337, 1998).     

Mixed problem for the wave equation with integrable potential in the case of two-point boundary conditions of distinct orders

We study a mixed problem for the wave equation with integrable potential and with two-point boundary conditions of distinct orders for the case in which the corresponding spectral problem may have multiple spectrum. Based on the resolvent approach in the Fourier method and the Krylov convergence acceleration trick for Fourier series, we obtain a classical solution u(x, t) of this problem under minimal constraints on the initial condition u(x, 0) = ?(x). We use the Carleson–Hunt theorem to prove the convergence almost everywhere of the formal solution series in the limit case of ?(x) ∈ L _p[0, 1], p > 1, and show that the formal solution is a generalized solution of the problem.     

Propagation of sound pulses in a homogeneous layer under an inhomogeneous half space

We consider the propagation of two-dimensional sound pulses in a homogeneous layer ?y ₁?y?0. It is bounded by a plane stratified inhomogeneous half spacey?0 on one side and a perfectly reflecting boundary on the other. A line source is situated in the layer. The boundary condition isφ=0 or?φ/?y=0 aty=?y ₁, whereφ is the acoustic velocity potential. We suppose that the velocity of wave propagationc is given byc ^?2=p?qe ^?αy iny>0, wherep, q, α are real and positive andp>q. It is equal to C′ in the layer where C′ is a constant. The method of dual integral transformation is used and the velocity potentialφ is obtained after using asymptotic expressions for some of the functions which are in the integrand. We obtain the incident, reflected, multiply-reflected and diffracted pulses in the layer.     

Stabilization by output of continuous and pulse-modulated uncertain systems

The system ? _i = ? _i (?) + x _i+2, \(i \in \overline {1,n - 2} \), ? _n?1 = ? _n?1(?) + u ₁, ? _n = ? _n (?) + u ₂,where ? _i (·) are nonanticipating functionals of an arbitrary nature with the following properties—\(\left| {{\varphi _i}\left( \cdot \right)} \right| \leqslant c\sum\nolimits_{k = 1}^i {\left| {{x_k}\left( t \right)} \right|} \), \(i \in \overline {1,n} \), c = const—and u ₁ and u ₂ are the controls is considered. It is assumed that only the outputs x ₁ and x ₂ are measurable. The problem of synthesis of both continuous and impulsive controls u1 and u2, which make the system globally asymptotically stable, is solved. The solution of the problem is based on the construction of the observer-based equations, the quadratic Lyapunov function, and the averaging method.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Two-Sided Estimates of Fourier Sums Lebesgue Functions with Respect to Polynomials Orthogonal on Nonuniform Grids

Let Ω = {t₀, t₁, …, t_N} and Ω_N = {x₀, x₁, …, x_N–1}, where x_j = (t_j + t_{j + 1})/2, j = 0, 1, …, N–1 be arbitrary systems of distinct points of the segment [–1, 1]. For each function f(x) continuous on the segment [–1, 1], we construct discrete Fourier sums S_{n, N}( f, x) with respect to the system of polynomials {p?_k,N(x)} _k=0 ^N–1 , forming an orthonormal system on nonuniform point systems Ω_N consisting of finite number N of points from the segment [–1, 1] with weight Δt_j = t_{j + 1}–t_j. We find the growth order for the Lebesgue function L_n,N (x) of the considered partial discrete Fourier sums S_n,N ( f, x) as n = O(δ _N ^?2/7 ), δ_N = max_{0≤ j≤N?1} Δt_j More exactly, we have a two-sided pointwise estimate for the Lebesgue function L_{n, N}(x), depending on n and the position of the point x from [–1, 1].     

Sets of Absolute Continuity for Harmonic Measure in NTA Domains

We show that if Ω is an NTA domain with harmonic measure ω and E??Ω is contained in an Ahlfors regular set, then \(\omega |_{E}\ll \mathcal {H}^{d}|_{E}\). Moreover, this holds quantitatively in the sense that for all τ>0ω obeys an A_∞-type condition with respect to \(\mathcal {H}^{d}|_{E^{\prime }}\), where E^′?E is so that ω(E?E^′)<τω(E), even though ?Ω may not even be locally \(\mathcal {H}^{d}\)-finite. We also show that, for uniform domains with uniform complements, if E??Ω is the Lipschitz image of a subset of \(\mathbb {R}^{d}\), then there is E^′?E with \(\mathcal {H}^{d}(E\backslash E^{\prime })<\tau \mathcal {H}^{d}(E)\) upon which a similar A_∞-type condition holds.     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

On the boundedness of generalized solutions of higher-order nonlinear elliptic equations with data from an Orlicz–Zygmund class

In the present paper, a 2mth-order quasilinear divergence equation is considered under the condition that its coefficients satisfy the Carathéodory condition and the standard conditions of growth and coercivity in the Sobolev space W^m,p(Ω), Ω ? Rⁿ, p > 1. It is proved that an arbitrary generalized (in the sense of distributions) solution u ∈ W₀^m,p (Ω) of this equation is bounded if m ≥ 2, n = mp, and the right-hand side of this equation belongs to the Orlicz–Zygmund space L(log L)^n?1(Ω).