Existence of a low rank or ℋ︁‐matrix approximant to the solution of a Sylvester equation

We consider the Sylvester equation AX?XB+C=0 where the matrix C∈?^n×m is of low rank and the spectra of A∈?^n×n and B∈?^m×m are separated by a line. We prove that the singular values of the solution X decay exponentially, that means for any ε∈(0,1) there exists a matrix X? of rank k=O(log(1/ε)) such that ∥X?X?∥₂?ε∥X∥₂. As a generalization we prove that if A,B,C are hierarchical matrices then the solution X can be approximated by the hierarchical matrix format described in Hackbusch (Computing 2000; 62 : 89–108). The blockwise rank of the approximation is again proportional to log(1/ε). Copyright © 2004 John Wiley & Sons, Ltd.     

On the Schur multiplier norm of matrices

The Schur product of two n×n complex matrices A=(a_ij), B=(b_ij) is defined by A°B=(a_ijb_ij. By a result of Schur [2], the algebra of n×n matrices with Schur product and the usual addition is a commutative Banach algebra under the operator norm (the norm of the operator defined on $\text{C}$ⁿ by the matrix). For a fixed matrix A, the norm of the operator B?A°B on this Banach algebra is called the Schur multiplier norm of A, and is denoted by ∥A∥^m. It is proved here that $\text{∥A∥=∥U}{}^1\text{AU∥}{}_{\mathrm{m}}$ for all unitary U (where ∥·∥ denotes the operator norm) iff A is a scalar multiple of a unitary matrix; and that ∥A∥_m=∥A∥ iff there exist two permutations P, Q, a p×p (1?p?n) unitary U, an (n?p)×(n?p)1 contraction C, and a nonnegative number λ such that

$\text{A=λP}\text{U}\text{0}\text{0}\text{C}\text{Q;}$

and this is so iff $\text{∥A°}\text{A}\text{?}\text{∥=∥A∥}{}^2$, where ā is the matrix obtained by taking entrywise conjugates of A.     

Monotone numerical schemes for a Dirichlet problem for elliptic operators in divergence form

We consider a second‐order differential operator A( x )=?∑?_ia_ij( x )?_j+ ∑?_j(b_j( 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 a_ij. 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 L₁ spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.     

On series of signed vectors and their rearrangements

Let x₁,…,x_m∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥x_i∥₂ ≤ 1 for all i. It is proved that there are signs ε₁,…,ε_m = ±1 such that where C₁, C₂ 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     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

An artificial boundary condition for an advection–diffusion equation

Consider the advection–diffusion equation: u₁ + au_x1 ? vδu = 0 in ?ⁿ × ?⁺ with initial data u⁰; the Support of u⁰ is contained in ?(x₁ < 0) and a: ?ⁿ → ? is positive. In order to approximate the full space solution by the solution of a problem in ? × ?⁺, we propose the artificial boundary condition: u₁ + au_x1 = 0 on ∑. We study this by means of a transmission problem: the error is an O(v²) for small values of the viscosity v.     

Longtime behavior for a nonlinear wave equation arising in elasto‐plastic flow

The paper studies the longtime behavior of solutions to the initial boundary value problem (IBVP) for a nonlinear wave equation arising in elasto‐plastic flow u_tt?div{|?u|^m?1?u}?λΔu_t+Δ²u+g(u)=f(x). It proves that under rather mild conditions, the dynamical system associated with above‐mentioned IBVP possesses a global attractor, which is connected and has finite Hausdorff and fractal dimension in the phase spaces X₁=H(Ω) × L²(Ω) and X=(H³(Ω)∩H(Ω)) × H(Ω), respectively. Copyright © 2008 John Wiley & Sons, Ltd.     

m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements

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 X_n = ^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 (X_n ? nX)/n ? ρ(C cos(τ₂log n + φ) + S sin(τ₂log n + φ)) →_n→∞ 0 almost surely and in L²; σ₂ and τ₂ 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     

Singular integral operators and norm ideals satisfying a quantitative variant of Kuroda's condition

A norm ideal C is said to satisfy condition (QK) if there exist constants 0<t<1 and 0<B<∞, such that ∥X^[k]∥_C?Bk^t∥X∥_C for every finite-rank operator X and every k∈N, where X^[k] denotes the direct sum of k copies of X. Let μ be a regular Borel measure whose support is contained in a unit cube Q in Rⁿ and let K_j be the singular integral operator on L²(Rⁿ,μ) with the kernel function (x_j-y_j)/|x-y|², 1?j?n. Let {Q_w:w∈W} be the usual dyadic decomposition of Q, i.e., {Q_w:|w|=?} is the dyadic partition of Q by cubes of the size 2^-?×?×2^-?. We show that if C satisfies (QK) and if ∥∑_w∈W2^|w|μ(Q_w)ξ_w⊗ξ_w∥_C^′<∞, where C^′ is the dual of C⁽⁰⁾ and {ξ_w:w∈W} is any orthonormal set, then K₁,…,K_n∈C^′. This is a very general obstruction result for the problem of simultaneous diagonalization of commuting tuples of self-adjoint operators modulo C.     

Iteratively reweighted least squares minimization for sparse recovery

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 ??₁‐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 ??₂(w)‐norm. If x⁽ⁿ⁾ is the solution at iteration step n, then the new weight w⁽ⁿ⁾ is defined by w := [|x|² + ε]^?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⁽ⁿ⁾ 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⁽ⁿ⁾ 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|² + ε]^?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.     

Computing projections via Householder transformations and Gram–Schmidt orthogonalizations

Let x * denote the solution of a linear least‐squares problem of the form where A is a full rank m × n matrix, m > n. Let r *= b ‐ A x * denote the corresponding residual vector. In most problems one is satisfied with accurate computation of x *. Yet in some applications, such as affine scaling methods, one is also interested in accurate computation of the unit residual vector r */∥ r *∥₂. The difficulties arise when ∥ r *∥₂ is much smaller than ∥ b ∥₂. Let x? and r? denote the computed values of x * and r *, respectively. Let εdenote the machine precision in our computations, and assume that r? is computed from the equality r? = b ‐A x? . Then, no matter how accurate x? is, the unit residual vector û = r? /∥ r? ∥₂ contains an error vector whose size is likely to exceed ε∥ b ∥₂/∥ r* ∥₂. That is, the smaller ∥ r* ∥₂ the larger the error. Thus although the computed unit residual should satisfy A^T û = 0 , in practice the size of ∥A^T û ∥₂ is about ε∥A∥₂∥ b ∥₂/∥ r* ∥₂. The methods discussed in this paper compute a residual vector, r? , for which ∥A^T r? ∥₂ is not much larger than ε∥A∥₂∥ r? ∥₂. Numerical experiments illustrate the difficulties in computing small residuals and the usefulness of the proposed safeguards. Copyright © 2004 John Wiley & Sons, Ltd.     

Time asymptotics for the polyharmonic wave equation in waveguides

Let Ω denote an unbounded domain in ?ⁿ having the form Ω=?^l×D with bounded cross‐section D??^n?l, and let m∈? be fixed. This article considers solutions u to the scalar wave equation ?u(t,x) +(?Δ)^mu(t,x) = f(x)e^?iωt satisfying the homogeneous Dirichlet boundary condition. The asymptotic behaviour of u as t→∞ is investigated. Depending on the choice of f ,ω and Ω, two cases occur: Either u shows resonance, which means that ∣u(t,x)∣→∞ as t→∞ for almost every x ∈ Ω, or u satisfies the principle of limiting amplitude. Furthermore, the resolvent of the spatial operators and the validity of the principle of limiting absorption are studied. Copyright © 2003 John Wiley & Sons, Ltd.     

A new model updating method for damped structural systems

In this paper, the following two are considered: Problem IQEP Given M_a∈ SR ^n×n, Λ=diag{λ₁, …, λ_p}∈ C ^p×p, X=[x₁, …, x_p]∈ C ^n×p, and both Λ and X are closed under complex conjugation in the sense that $\lambda_{2j} = \bar{\lambda}_{2j-1} \in {\mathbf{C}}In this paper, the following two are considered: Problem IQEP Given M_a∈ SR ^n×n, Λ=diag{λ₁, …, λ_p}∈ C ^p×p, X=[x₁, …, x_p]∈ C ^n×p, and both Λ and X are closed under complex conjugation in the sense that $\lambda_{2j} = \bar{\lambda}_{2j-1} \in {\mathbf{C}}$, x_2j=x?_2j?1∈ C ⁿ for j = 1,…,l, and λ_k∈ R , x_k∈ R ⁿ for k=2l+1,…,p, find real‐valued symmetric (2r+1)‐diagonal matrices D and K such that ∥M_aXΛ²+DXΛ+KX∥=min. Problem II Given real‐valued symmetric (2r+1)‐diagonal matrices D_a, K_a∈ R ^n×n, find $(\hat{D},\hat{K}) \in {\mathscr{S}}_{DK}$ such that $\|\hat{D}-D_a \|^2+ \| \hat{K}-K_a \|^2=\rm{inf}_{(D,K) \in {\mathscr{S}}_{DK}}(\|D-D_a\|^2+\|K-K_a\|^2)$, where ??_DK is the solution set of IQEP. By applying the Kronecker product and the stretching function of matrices, the general form of the solution of Problem IQEP is presented. The expression of the unique solution of Problem II is derived. A numerical algorithm for solving Problem II is provided. Copyright © 2009 John Wiley & Sons, Ltd.     

Variational Inequalities: an Elementary Approach

We will deal with the following problem: Let M be an n×n matrix with real entries. Under which conditions the family of inequalities: x∈? ⁿ ;x?0;M·x?0has non–trivial solutions? We will prove that a sufficient condition is given by m_i,j+m_j,i?0 (1?i,j?n); from this result we will derive an elementary proof of the existence theorem for Variational Inequalities in the framework of Monotone Operators.     

Subelliptic Estimates for a Class of Degenerate Elliptic Integro-Differential Operators

In this paper we prove subelliptic estimates for operators of the form Δ_x + λ² (x)S in ?^N = ? × ?, where the operator S is an elliptic integro - differential operator in ?^N and λ is a nonnegative Lipschitz continuous function.     

Construction of translation planes from t-spread sets

A t-spread set [1] is a set $\text{C}$ of (t + 1) × (t + 1) matrices over GF(q) such that ∥C∥ = q^t+1, 0 ? C, I?C, and det(X ? Y) ≠ 0 if X and Y are distinct elements of $\text{C}$. The amount of computation involved in constructing t-spread sets is considerable, and the following construction technique reduces somewhat this computation. Construction: Let $\text{G}$ be a subgroup of GL(t + 1, q), (the non-singular (t + 1) × (t + 1) matrices over GF(q)), such that ∥G∥|a^t+1, and det (G ? H) ≠ 0 if G and H are distinct elements of $\text{G}$. Let A₁, A₂, …, A_n?GL(t + 1, q) such that det(A_i ? G) ≠ 0 for i = 1, …, n and all G?G, and det(A_i ? A_jG) ≠ 0 for i > j and all G?G. Let $\text{C = \&{0\&} ∪ G ∪ A}{}_1\text{G ∪ … ∪ A}{}_{\mathrm{n}}\text{G}$, and ∥C∥ = q^t+1. Then $\text{C}$ is a t-spread set. A t-spread set can be used to define a left V ? W system over V(t + 1, q) as follows: x + y is the vector sum; let e?V(t + 1, q), then xoy = yM(x) where M(x) is the unique element of $\text{C}$ with x = eM(x). Theorem: Let$\text{C}$be a t-spread set and F the associatedV ? Wsystem; the left nucleus = {y | CM(y) = C}, and the middle nucleus = }y | M(y)C = C}. Theorem: For$\text{C}$constructed as aboveG ? {M(x) | x?N_λ}. This construction technique has been applied to construct a V ? W system of order 25 with ∥N_λ∥ = 6, and ∥N_μ∥ = 4. This system coordinatizes a new projective plane.     

Global attractor and decay estimates of solutions to a class of nonlinear evolution equations

In this work, we prove the existence of global attractor for the nonlinear evolution equation u_tt?Δu?Δu_t?Δu_tt + g(x, u)=f(x) in X=(H²(Ω)∩H(Ω)) × (H²(Ω)∩H(Ω)). This improves a previous result of Xie and Zhong in (J. Math. Anal. Appl. 2007; 336 :54–69.) concerning the existence of global attractor in H(Ω) × H(Ω) for a similar equation. Further, the asymptotic behavior and the decay property of global solution are discussed. Copyright © 2010 John Wiley & Sons, Ltd.     

Compactness methods in the theory of homogenization II: Equations in non-divergence form

We prove C^{0, α}, C^{1, α} and C^{1, 1} a priori estimates for solutions of boundary value problems for elliptic operators with periodic coefficients of the form Σ,^j=1a^{i j}(x/?)δ²/δx_iδx_j. 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.     

On Σ1-definable Functions Provably Total in I ∏

We prove the following theorem: Let φ(x) be a formula in the language of the theory PA^? of discretely ordered commutative rings with unit of the form ?yφ′(x,y) with φ′ and let ∈ Δ₀ and let fφ: ? → ? such that f_φ(x) = y iff φ′(x,y) & (?z < y) φ′(x,z). If I ∏ ∈(?x ≥ 0), φ then there exists a natural number K such that I ∏ ? ?y?x(x > y ? ?φ(x) < x^K). Here I ∏₁^? denotes the theory PA^? plus the scheme of induction for formulas φ(x) of the form ?yφ′(x,y) (with φ′) with φ′ ∈ Δ₀.     

New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities

This paper introduces new tight frames of curvelets to address the problem of finding optimally sparse representations of objects with discontinuities along piecewise C² edges. Conceptually, the curvelet transform is a multiscale pyramid with many directions and positions at each length scale, and needle‐shaped elements at fine scales. These elements have many useful geometric multiscale features that set them apart from classical multiscale representations such as wavelets. For instance, curvelets obey a parabolic scaling relation which says that at scale 2^?j, each element has an envelope that is aligned along a “ridge” of length 2^?j/2 and width 2^?j. We prove that curvelets provide an essentially optimal representation of typical objects f that are C² except for discontinuities along piecewise C² curves. Such representations are nearly as sparse as if f were not singular and turn out to be far more sparse than the wavelet decomposition of the object. For instance, the n‐term partial reconstruction f obtained by selecting the n largest terms in the curvelet series obeys This rate of convergence holds uniformly over a class of functions that are C² except for discontinuities along piecewise C² curves and is essentially optimal. In comparison, the squared error of n‐term wavelet approximations only converges as n^?1 as n → ∞, which is considerably worse than the optimal behavior. © 2003 Wiley Periodicals, Inc.