A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.     

A partially isochronous splitting algorithm for three-block separable convex minimization problems

During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

Complexity of function systems over a finite field in the class of polarized polynomial forms

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L _q ^PPF (n,m) = q ⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2 ⁿ and L₃^PPF (n,m) = 3 ⁿ for all n ≥ 1 and m ≥ 2.     

Oscillation of the measure of irrationality function in the multidimensional case

It is proved that, for almost all pairs of n × m matrices Θ, Θ', in the cases m = 1 and n = 2 or m ≥ 2 and n = 1, the difference between the measure of irrationality functions ψΘ ? ψΘ' oscillates an infinite number of times as t → +∞.     

Construction of optimal quadrature formulas for Fourier coefficients in Sobolev space $L_{2}^{(m)}(0,1)$

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the \(L_{2}^{(m)}(0,1)\) space for numerical calculation of Fourier coefficients. Using the S.L.Sobolev’s method, we obtain new optimal quadrature formulas of such type for N+1≥m, where N+1 is the number of nodes. Moreover, explicit formulas for the optimal coefficients are obtained. We study the order of convergence of the optimal formula for the case m=1. The obtained optimal quadrature formulas in the \(L_{2}^{(m)}(0,1)\) space are exact for P _m?1(x), where P _m?1(x) is a polynomial of degree m?1. Furthermore, we present some numerical results, which confirm the obtained theoretical results.     

Symmetries of Fundamental Solutions and Their Application in Continuum Mechanics

This paper is a brief survey of the recent results in problems of approximating functions by solutions of homogeneous elliptic systems of PDEs on compact sets in the plane in the norms of C^m spaces, m ≥ 0. We focus on general second-order systems. For such systems the paper complements the recent survey by M. Mazalov, P. Paramonov, and K. Fedorovskiy (2012), where the problems of C^m approximation of functions by holomorphic, harmonic, and polyanalytic functions as well as by solutions of homogeneous elliptic PDEs with constant complex coefficients were considered.     

Generalized symmetric ADMM for separable convex optimization

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists of p block variables while the other has q block variables, where \(p \ge 1\) and \(q \ge 1\) are two integers. The two grouped variables are updated in a Gauss–Seidel scheme, while the variables within each group are updated in a Jacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case \({\mathcal {O}}(1/t)\) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.     

Normal families of meromorphic functions and shared functions

The paper is devoted to the normal families of meromorphic functions and shared functions. Generalizing a result of Chang (2013), we prove the following theorem. Let h (≠≡ 0,∞) be a meromorphic function on a domain D and let k be a positive integer. Let F be a family of meromorphic functions on D, all of whose zeros have multiplicity at least k + 2, such that for each pair of functions f and g from F, f and g share the value 0, and f^(k) and g^(k) share the function h. If for every f ∈ F, at each common zero of f and h the multiplicities m_f for f and m_h for h satisfy m_f ≥ m_h + k + 1 for k > 1 and m_f ≥ 2m_h + 3 for k = 1, and at each common pole of f and h, the multiplicities nf for f and nh for h satisfy n_f ≥ n_h + 1, then the family F is normal on D.     

On Substructure Densities of Hypergraphs

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.     

On Schwarzian Triangle Functions,Automorphic Forms and a Generalization of Ramanujan’s Triple Differential Equations

Let G be the group of the fractional linear transformations generated by

$$T(\tau ) = \tau + \lambda ,S(\tau ) = \frac{{\tau \cos \frac{\pi }{n} + \sin \frac{\pi }{n}}}{{ - \tau \sin \frac{\pi }{n} + \cos \frac{\pi }{n}}};$$

where

$$\lambda = 2\frac{{\cos \frac{\pi }{m} + \cos \frac{\pi }{n}}}{{\sin \frac{\pi }{n}}};$$

m, n is a pair of integers with either n ≥ 2,m ≥ 3 or n ≥ 3,m ≥ 2; τ lies in the upper half plane H.

A fundamental set of functions f₀, f_i and f_∞ automorphic with respect to G will be constructed from the conformal mapping of the fundamental domain of G. We derive an analogue of Ramanujan’s triple differential equations associated with the group G and establish the connection of f₀, f_i and f_∞ with a family of hypergeometric functions.     

The influence of the integral manifold shape on the onset of relaxation oscillations

The relaxation oscillations are studied of a singularly perturbed system of ordinary differential equations with m slow and n fast variables (m × n) in the two cases: (1) m = n = 1 (1 × 1) and (2) m = 2, n = 1 (2 × 1). As sufficient conditions for the existence of relaxation oscillations there some general class is described of the functions determining the slow manifold for this system.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon P in \({\mathbb{R}^2}\) with m edges can be represented by inequalities p ₁ ≥ 0, . . ., p _n ≥ 0, where the p _i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies \({s(m, k) \leq n(m, k) \leq (1+\varepsilon_m) s(m, k)}\) with s(m,k) ? max {m/k, log₂ m} and \({\varepsilon_m \rightarrow 0}\) as \({m \rightarrow \infty}\). This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p ₁ > 0, . . ., p _n >  0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.     

Analysing the Wu metric on a class of eggs in ℂ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> – I

We study the Wu metric on convex egg domains of the form

$$E_{2m} = \big\{ z \in \mathbb{C}^{n}: \vert{z_{1}} \vert^{2m} + \vert {z_{2}} \vert^{2} + {\cdots} + \vert {z_{n-1}} \vert^{2} + \vert {z_{n}} \vert^{2} <1 \big\}, $$

where m ≥ 1/2,m ≠ 1. The Wu metric is shown to be real analytic everywhere except on a lower dimensional subvariety where it fails to be C ²-smooth. Overall however, the Wu metric is shown to be continuous when m = 1/2 and even C ¹-smooth for each m > 1/2, and in all cases, a non-Kähler Hermitian metric with its holomorphic curvature strongly negative in the sense of currents. This gives a natural answer to a conjecture of S. Kobayashi and H. Wu for such E _2m .     

Modified boundary element method for problems on oscillations of flat membranes

In the space L ² of real-valued measurable 2π-periodic functions that are square summable on the period [0, 2π], the Jackson-Stechkin inequality

$$E_n (f) \leqslant \mathcal{K}_n (\delta ,\omega )\omega (\delta ,f), f \in L^2 $$

, is considered, where E _n (f) is the value of the best approximation of the function f by trigonometric polynomials of order at most n and ω(δ, f) is the modulus of continuity of the function f in L ² of order 1 or 2. The value

$$\mathcal{K}_n (\delta ,\omega ) = \sup \left\{ {\frac{{E_n (f)}}{{\omega (\delta ,f)}}:f \in L^2 } \right\}$$

is found at the points δ = 2π/m (where m ∈ ?) for m ≥ 3n ² + 2 and ω = ω ₁ as well as for m ≥ 11n ⁴/3 ? 1 and ω = ω ₂.

     

Construction of a linear Pfaff system with <Emphasis Type="Italic">m</Emphasis>-dimensional time and with given characteristic set and lower characteristic set

For any positive integers n ≥ 1 and m ≥ 2, we give a constructive proof of the existence of linear n-dimensional Pfaff systems with m-dimensional time and with infinitely differentiable coefficient matrices such that the characteristic and lower characteristic sets of these systems are given sets that are the graphs of a concave continuous function and a convex continuous function, respectively, defined and monotone decreasing on simply connected closed bounded convex domains of the space ?^m?1.     

On a functional equation related to derivations in prime rings

In this paper we prove the following result. Let m ≥ 1, n ≥ 1 be fixed integers and let R be a prime ring with m + n + 1 ≤ char(R) or char(R) = 0. Suppose there exists an additive nonzero mapping D : R → R satisfying the relation 2D(x ^n+m+1) = (m + n + 1)(x ^m D(x)x ⁿ + x ⁿ D(x)x ^m ) for all \({x\in R}\). In this case R is commutative and D is a derivation.     

Thom-Sebastiani properties of Kohn-Rossi cohomology of compact connected strongly pseudoconvex CR manifolds

Let X_1 and X_2 be two compact connected strongly pseudoconvex embeddable Cauchy-Riemann(CR) manifolds of dimensions 2m-1 and 2n-1 in C~(m+1)and C~(n+1), respectively. We introduce the ThomSebastiani sum X = X_1 ⊕X_2which is a new compact connected strongly pseudoconvex embeddable CR manifold of dimension 2m+2n+1 in C~(m+n+2). Thus the set of all codimension 3 strongly pseudoconvex compact connected CR manifolds in Cn+1for all n 2 forms a semigroup. X is said to be an irreducible element in this semigroup if X cannot be written in the form X_1 ⊕ X_2. It is a natural question to determine when X is an irreducible CR manifold. We use Kohn-Rossi cohomology groups to give a necessary condition of the above question. Explicitly,we show that if X = X_1 ⊕ X_2, then the Kohn-Rossi cohomology of the X is the product of those Kohn-Rossi cohomology coming from X_1 and X_2 provided that X_2 admits a transversal holomorphic S~1-action.     

Picard dimension of signed radial Kato measures

The Picard dimension dimμ of a signed local Kato measure μ on the punctured unit ball in R^d, d ≥ 2, is the cardinal number of the set of extremal rays of the convex cone of all continuous solutions u ≥ 0 of the time-independent SchrSdinger equation Δu -- uμ = 0 on the punctured ball 0 〈 ｜｜x｜｜ 〈 1, with vanishing boundary values on the sphere ｜｜x｜｜ = 1. Using potential theory associated with the Schrodinger operator we prove, in this paper, that the dimμ for a signed radial Kato measure is 0, 1 or ＋∞. In particular, we obtain the Picard dimension of locally Holder continuous functions P proved by Nakai and Tada by other methods.