首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (where m < N), vectors x ∈ ?N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φx even though Φ?1(y) is typically an (N ? m)—dimensional hyperplane; in addition, x is then equal to the element in Φ?1(y) of minimal ??1‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Φ?1(y) with smallest ??2(w)‐norm. If x(n) is the solution at iteration step n, then the new weight w(n) is defined by w := [|x|2 + ε]?1/2, i = 1, …, N, for a decreasing sequence of adaptively defined εn; this updated weight is then used to obtain x(n + 1) and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x(n) converges for all y, regardless of whether Φ?1(y) contains a sparse vector. If there is a sparse vector in Φ?1(y), then the limit is this sparse vector, and when x(n) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight w = [|x|2 + ε]?1+τ/2, i = 1, …, N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.  相似文献   

2.
We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}n, and k parties, who have noisy version of the source bits yi ∈ {0, 1}n, when for all i and j, it holds that P [y = xj] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions fi: {0, 1}n → {0, 1} such that P [f1(y1) = … = fk(yk)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function fi may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by fi(yi) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005  相似文献   

3.
A k-graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ? E sicj tjat f|α is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number ? of edges in a tight k-graph with n vertices are given. We conjecture that ? for every n and prove the equality when 2n + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.  相似文献   

4.
We study the following initial and boundary value problem: In section 1, with u0 in L2(Ω), f continuous such that f(u) + ? non-decreasing for ? positive, we prove the existence of a unique solution on (0,T), for each T > 0. In section 2 it is proved that the unique soluition u belongs to L2(0, T; H ∩ H2) ∩ L(0, T; H) if we assume u0 in H and f in C1(?,?). Numerical results are given for these two cases.  相似文献   

5.
We prove that if there exists a t − (v, k, λ) design satisfying the inequality for some positive integer j (where m = min{j, vk} and n = min {i, t}), then there exists a t − (v + j, k, λ ()) design. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 107–112, 1999  相似文献   

6.
We consider a domain Ω in ?n of the form Ω = ?l × Ω′ with bounded Ω′ ? ?n?l. In Ω we study the Dirichlet initial and boundary value problem for the equation ? u + [(? ? ?… ? ?)m + (? ? ?… ? ?)m]u = fe?iωt. We show that resonances can occur if 2ml. In particular, the amplitude of u may increase like tα (α rational, 0<α<1) or like in t as t∞∞. Furthermore, we prove that the limiting amplitude principle holds in the remaining cases.  相似文献   

7.
We study the maximal function Mf(x) = sup |f(x + y, t)| when Ω is a region in the (y,t) Ω upper half space R and f(x, t) is the harmonic extension to R+N+1 of a distribution in the Besov space Bαp,q(RN) or in the Triebel-Lizorkin space Fαp,q(RN). In particular, we prove that when Ω= {|y|N/ (N-αp) < t < 1} the operator M is bounded from F (RN) into Lp (RN). The admissible regions for the spaces B (RN) with p < q are more complicated.  相似文献   

8.
It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector Xn = t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (Xn ? nX)/n ? ρ(C cos(τ2log n + φ) + S sin(τ2log n + φ)) →n→∞ 0 almost surely and in L2; σ2 and τ2 denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004  相似文献   

9.
We prove C0, α, C1, α and C1, 1 a priori estimates for solutions of boundary value problems for elliptic operators with periodic coefficients of the form Σ,j=1ai j(x/?)δ2/δxiδxj. The constants in these estimates are independent of the small parameter ?, and hence our results imply strengthened versions of the classical averaging theorems. These results generalize to a wide class of linear operators in non-divergence form, including equations with lower-order terms and nonuniformly oscillating coefficients, as well as to certain nonlinear problems, which we discuss in the last section.  相似文献   

10.
In this paper we study weighted function spaces of type B(?n, Q(x)) and F(?n, Q(x)), where Q(x) is a weight function of at most polynomial growth. Of special interest are the weight functions Q(x) = (1 + |x|2)α/2 with α ? ?. The main result deals with estimates for the entropy numbers of compact embeddings between spaces of this type.  相似文献   

11.
A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Qn)=?log2n?+1 which matches the lower bound, and that Det(K)=?log3(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hn)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory  相似文献   

12.
We consider a second‐order differential operator A( x )=??iaij( x )?j+ ?j(bj( x )·)+c( x ) on ?d, on a bounded domain D with Dirichlet boundary conditions on ?D, under mild assumptions on the coefficients of the diffusion tensor aij. The object is to construct monotone numerical schemes to approximate the solution of the problem A( x )u( x )=µ( x ), x ∈D, where µ is a positive Radon measure. We start by briefly mentioning questions of existence and uniqueness introducing function spaces needed to prove convergence results. Then, we define non‐standard stencils on grid‐knots that lead to extended discretization schemes by matrices possessing compartmental structure. We proceed to discretization of elliptic operators, starting with constant diffusion tensor and ending with operators in divergence form. Finally, we discuss W‐convergence in detail, and mention convergence in C and L1 spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.  相似文献   

13.
This paper is a continuation of [8]. We study weighted function spaces of type B and F on the Euclidean space Rn, where u is a weight function of at most exponential growth. In particular, u(χ (±|χ|) is an admissible weight. We deal with atomic decompositions of these spaces. Furthermore, we prove that the spaces B and F are isomorphic to the corresponding unweighted spaces B and F.  相似文献   

14.
This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?n, w(x)) and F (?n, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b2(x) b(x, D) b1(x), where b1(x) and b2(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L2.  相似文献   

15.
This paper is devoted to the study of the Cauchy problem of incompressible magneto‐hydrodynamics system in the framework of Besov spaces. In the case of spatial dimension n?3, we establish the global well‐posedness of the Cauchy problem of an incompressible magneto‐hydrodynamics system for small data and the local one for large data in the Besov space ? (?n), 1?p<∞ and 1?r?∞. Meanwhile, we also prove the weak–strong uniqueness of solutions with data in ? (?n)∩L2(?n) for n/2p+2/r>1. In the case of n=2, we establish the global well‐posedness of solutions for large initial data in homogeneous Besov space ? (?2) for 2<p<∞ and 1?r<∞. Copyright © 2008 John Wiley & Sons, Ltd.  相似文献   

16.
Given a normalized Maxwellian μ and n ≥ 1, we establish the global‐in‐time validity of a diffusive expansion for a solution Fε to the rescaled Boltzmann equation (diffusive scaling) inside a periodic box ??3. We assume that in the initial expansion (0.1) at t = 0, the fluid parts of these fm(0,x,v) have arbitrary divergence‐free velocity fields as well as temperature fields for all 1 ≤ mn while f1(0,x,v) has small amplitude in H2. For m ≥ 2, these fm(t,x,v) are determined by a sequence of linear Navier‐Stokes‐Fourier systems iteratively. More importantly, the remainder f(t,x,v) is proven to decay in time uniformly in ε via a unified nonlinear energy method. In particular, our results lead to an error estimate for f1(t,x,v), the well‐known Navier‐Stokes‐Fourier approximation, and beyond. The collision kernel Q includes hard‐sphere, the cutoff inverse‐power, as well as the Coulomb interactions. © 2005 Wiley Periodicals, Inc.  相似文献   

17.
By using the LITTLEWOOD matrices A2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A2n: l(LP) → l(LP)‖ completely. The result is compared with the norms ‖A2n: ll‖, which are calculated implicitly in PIETSCH [6].  相似文献   

18.
Let x1,…,xm∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥xi2 ≤ 1 for all i. It is proved that there are signs ε1,…,εm = ±1 such that where C1, C2 are some numerical constants. It is also proved that there are signs ε,…,ε = ±1 and a permutation π of {1,…,m} such that where C is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011  相似文献   

19.
We consider the following singularly perturbed Neumann problem: where Δ = Σ ?2/?x is the Laplace operator, ? > 0 is a constant, Ω is a bounded, smooth domain in ?N with its unit outward normal ν, and f is superlinear and subcritical. A typical f is f(u) = up where 1 < p < +∞ when N = 2 and 1 < p < (N + 2)/(N ? 2) when N ≥ 3. We show that there exists an ?0 > 0 such that for 0 < ? < ?0 and for each integer K bounded by where αN, Ω, f is a constant depending on N, Ω, and f only, there exists a solution with K interior peaks. (An explicit formula for αN, Ω, f is also given.) As a consequence, we obtain that for ? sufficiently small, there exists at least [αN, Ωf/?N (|ln ?|)N] number of solutions. Moreover, for each m ∈ (0, N) there exist solutions with energies in the order of ?N?m. © 2006 Wiley Periodicals, Inc.  相似文献   

20.
We consider the equation (?1)m?m (p?mu) + ?u = ? in ?n × (0, ∞) for arbitrary positive integers m and n and under the assumptions p ? 1, ? ? C(?n) and p > 0. Even if the differential operator (?1)m?m (p?mu) has no eigenvalues, the solution u(x,t) may increase as t → ∞ for 2mn. For this case, we derive necessary and sufficient conditions for the convergence of u(x,t) as t → ∞. Furthermore, we characterize the functions occurring in these conditions as solutions of the homogeneous static equation (?1)m?m (p?mu) = 0, which satisfy appropriate asymptotic conditions at infinity. We also give an asymptotic characterization of the static limit.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号