Analysis of orthogonal multi-matching pursuit under restricted isometry property

Orthogonal multi-matching pursuit(OMMP)is a natural extension of orthogonal matching pursuit(OMP)in the sense that N(N≥1)indices are selected per iteration instead of 1.In this paper,the theoretical performance of OMMP under the restricted isometry property(RIP)is presented.We demonstrate that OMMP can exactly recover any K-sparse signal from fewer observations y=φx,provided that the sampling matrixφsatisfiesδKN-N+1+(K/N)~(1/2)θKN-N+1,N1.Moreover,the performance of OMMP for support recovery from noisy observations is also discussed.It is shown that,for l_2 bounded and l_∞bounded noisy cases,OMMP can recover the true support of any K-sparse signal under conditions on the restricted isometry property of the sampling matrixφand the minimum magnitude of the nonzero components of the signal.     

Regular Splitting and Potential Reduction Method for Solving Quadratic Programming Problem with Box Constraints

A regular splitting and potential reduction method is presented for solving a quadratic programming problem with box constraints (QPB) in this paper. A general algorithm is designed to solve the QPB problem and generate a sequence of iterative points. We show that the number of iterations to generate an e-minimum solution or an e-KKT solution by the algorithm is bounded by O( nlog(1 )), and the total running time is bounded by O(n2(n logn log1/ε)(n/εlog1/ε logn)) arithmetic operations.     

Two algorithms for two-phase Stefan type problems

In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.     

Joint optimization traffic signal control for an urban arterial road

This paper considers the optimal traffic signal setting for an urban arterial road. By introducing the concepts of synchronization rate and non-synchronization degree, a mathematical model is constructed and an optimization problem is posed. Then, a new iterative algorithm is developed to solve this optimal traffic control signal setting problem. Convergence properties for this iterative algorithm are established. Finally, a numerical example is solved to illustrate the effectiveness of the method.     

UPDATING AND DOWNDATING FOR PARAMETER ESTIMATION WITH BOUNDED UNCERTAIN DATA

The bounded parameter estimation problem and its solution lead to more meaningful results. Its superior performance is due to the fact that the new method guarantees that the effect of the uncertainties will never be unnecessarily overestimated. We then consider how to update and downdate the bounded parameter estimation problem. When updating and downdating of SVD are used to the new problem, special technologies are taken to avoid forming U and V explicitly, then increase the algorithm performance. Because of the link between the bounded parameter estimation and Tikhonov regularization procedure, we point out that our algorithms can also be used to modify regularization problem.     

Cooley-Tukey FFT在高维的算法

A new fast algorithm is presented for multidimensional DFT in this paper. This algorithm is derived based on an interesting coding technique for multidimensional integral point, named the technique vector coding. And called the algorithm VCFFT (vector coding fast Fourier transform). Since the VC-FFT is the extension of Cooley-Tukey algorithm from one-dimensional to multidimensional, its structure of program is simple as Cooley-Tukey FFT, and significantly reduces multiplications and recursive stages.     

A method of estimating computational complexity based on input conditions for N-vehicle problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

Torsion Completeness of Sylow <Emphasis Type="Italic">p</Emphasis>-Groups in Semisimple Group Rings

Let G be an abelian p-group and K be a field of the first kind with respect to p of char K ≠p and of sp(K) = N or NU {0}. Then it is shown that the normed Sylow p-subgroup S(KG) is torsion complete if and only if G is bounded (Theorem 1). An analogous fact is proved for the case when K is of the second kind (Theorem 2). These completely settle a conjecture posed by us in Compt. Rend. Acad. Bulg. Sci. (1993) and are also a supplement to our result in the modular case published in Acta Math. Hungar. (1997).     

AN INTERIOR TRUST REGION ALGORITHM FOR NONLINEAR MINIMIZATION WITH LINEAR CONSTRAINTS

AbstractAn interior trust-region-based algorithm for linearly constrained minimization problems is proposed and analyzed. This algorithm is similar to trust region algorithms for unconstrained minimization: a trust region subproblem on a subspace is solved in each iteration. We establish that the proposed algorithm has convergence properties analogous to those of the trust region algorithms for unconstrained minimization. Namely, every limit point of the generated sequence satisfies the Krush-Kuhn-Tucker (KKT) conditions and at least one limit point satisfies second order necessary optimality conditions. In addition, if one limit point is a strong local minimizer and the Hessian is Lipschitz continuous in a neighborhood of that point, then the generated sequence converges globally to that point in the rate of at least 2-step quadratic. We are mainly concerned with the theoretical properties of the algorithm in this paper. Implementation issues and adaptation to large-scale problems will be addressed in a     

Tensor Banach algebras of projective type. II. Thel 1 case

It is shown that the tensor Banach functor of projective type \(\hat{T}_{K} \) [1] corresponding to the complete normed fieldK is quasiidempotent on infinite-dimensionall ₁ spaces, i.e., $$\hat{T}_{K} (\theta _{K} (\hat{T}_{K} (l_1 (M.K)))) \cong \hat{T}_K (l_1 (M.K)).$$ whereM is an infinite set and θ _K is the forgetful functor. Anl ₁ realization of the Banach algebra \(\hat{T}_{K} (l_1 (M.K))\) is constructed.     

Principal Eigenvalue of p-Laplacian Operator in Exterior Domain

We consider an eigenvalue problem of the form $$\left.\begin{array}{cl}-\Delta_{p} u = \lambda\, K(x)|u|^{p-2}u \quad \mbox{in}\quad \Omega^e\\ u(x) =0 \quad \mbox{for}\quad \partial \Omega\\ u(x) \to 0 \quad \mbox{as}\quad |x| \to \infty,\end{array} \right \}$$ where \({\Omega \subset \mathrm{I\!R\!}^N}\) is a simply connected bounded domain, containing the origin, with C ² boundary \({\partial \Omega}\) and \({\Omega^e:=\mathrm{I\!R\!^N} \setminus \overline{\Omega}}\) is the exterior domain, \({1 < p < N, \Delta_{p}u:={\rm div}(|\nabla u|^{p-2} \nabla u)}\) is the p-Laplacian operator and \({K \in L^{\infty}(\Omega^e) \cap L^{N/p}(\Omega^e)}\) is a positive function. Existence and properties of principal eigenvalue λ ₁ and its corresponding eigenfunction are established which are generally known in bounded domain or in \({\mathrm{I\!R\!}^N}\) . We also establish the decay rate of positive eigenfunction as \({|x| \to \infty}\) as well as near ?Ω.     

A-Systems, Independent Functions, and Sets Bounded in Spaces of Measurable Functions

Let $U \subset L_o ([0,1],\mathcal{M},m)$ be a set of Lebesgue measurable functions. Suppose also that two seminormed spaces of real number sequences are given: $\mathcal{A}$ and $\mathcal{B}$ . We study $\left( {\mathcal{A},\mathcal{B}} \right)$ -sets U defined by the classes $\mathcal{A}$ and $\mathcal{B}$ as follows: $\forall a = (a_n ) \in \mathcal{A}, \forall (f_n (t)) \in u^\mathbb{N} $ (or for sequences similar to $(f_n (t))$ ) $\exists E = E(a) \subset [0,1], mE = 1$ such that $\{ a_n f_n (t)\} 1_E (t)\} \in \mathcal{B}, t \in [0,1]$ . We consider three versions of the definition of $\left( {\mathcal{A},\mathcal{B}} \right)$ -sets, one of which is based on functions independent in the probability sense. The case ${\mathcal{B}}=l_\infty$ is studied in detail. It is shown that $({\mathcal{A}},l_\infty)$ -independent sets are sets bounded or order bounded in some well-known function spaces (L _p , L _p,q , etc.) constructed with respect to the Lebesgue measure. A characterization of such sets in terms of seminormed spaces of number sequences is given. The (l ₁,c _°)- and $(\mathcal{A},l_1 )$ -sets were studied by E. M. Nikishin.     

Density of primes in l-th power residues

Given a prime number l, a finite set of integers S?=?{a ₁, ...,a _m } and m many l-th roots of unity $\zeta_l^{r_i}, i=1, \ldots ,m$ we study the distribution of primes p in ?(ζ _l ) such that the l-th residue symbol of a _i with respect to p is $\zeta_l^{r_i}, \mbox{ for all } i$ . We find out that this is related to the degree of the extension $\mathbb{Q}(a_1^{\frac{1}{l}}, \ldots ,a_m^{\frac{1}{l}})/\mathbb{Q}$ . We give an algorithm to compute this degree. Also we relate this degree to rank of a matrix obtained from S?=?{a ₁, ...,a _m }. This latter argument enables one to describe the degree $\mathbb{Q}(a_1^{\frac{1}{l}}, \ldots ,a_m^{\frac{1}{l}})/\mathbb{Q}$ in much simpler terms.     

A lower bound on the barrier parameter of barriers for convex cones

Let ${K \subset \mathbb R^n}$ be a regular convex cone, let ${e_1,\ldots,e_n \in \partial K}$ be linearly independent points on the boundary of a compact affine section of the cone, and let ${x^* \in K^{0}}$ be a point in the relative interior of this section. For k =  1, . . . , n, let l _k be the line through the points e _k and x ^*, let y _k be the intersection point of l _k with ${\partial K}$ opposite to e _k , and let z _k be the intersection point of l _k with the linear subspace spanned by all points e _l , l =  1, . . . , n except e _k . We give a lower bound on the barrier parameter ν of logarithmically homogeneous self-concordant barriers ${F: K^{0}\to \mathbb R}$ on K in terms of the projective cross-ratios ${q_k = (e_k,x^*;y_k,z_k)}$ . Previously known lower bounds by Nesterov and Nemirovski can be obtained from our result as a special case. As an application, we construct an optimal barrier for the epigraph of the ${||\cdot||_{\infty}}$ -norm in ${\mathbb R^n}$ and compute lower bounds on the barrier parameter for the power cone and the epigraph of the ${||\cdot||_p}$ -norm in ${\mathbb R^2}$ .     

Uniqueness of diffusion operators and capacity estimates

Let Ω be a connected open subset of R ^d . We analyse L ₁-uniqueness of real second-order partial differential operators ${H = - \sum^d_{k,l=1} \partial_k c_{kl} \partial_l}$ and ${K = H + \sum^d_{k=1}c_k \partial_k + c_0}$ on Ω where ${c_{kl} = c_{lk} \in W^{1,\infty}_{\rm loc}(\Omega), c_k \in L_{\infty,{\rm loc}}(\Omega), c_0 \in L_{2,{\rm loc}}(\Omega)}$ and C(x) = (c _kl (x)) > 0 for all ${x \in \Omega}$ . Boundedness properties of the coefficients are expressed indirectly in terms of the balls B(r) associated with the Riemannian metric C ^?1 and their Lebesgue measure |B(r)|. First, we establish that if the balls B(r) are bounded, the Täcklind condition ${\int^\infty_R dr r({\rm log}|B(r)|)^{-1} = \infty}$ is satisfied for all large R and H is Markov unique then H is L ₁-unique. If, in addition, ${C(x) \geq \kappa (c^{T} \otimes c)(x)}$ for some ${\kappa > 0}$ and almost all ${x \in \Omega}$ , ${{\rm div} c \in L_{\infty,{\rm loc}}(\Omega)}$ is upper semi-bounded and c ₀ is lower semi-bounded, then K is also L ₁-unique. Secondly, if the c _kl extend continuously to functions which are locally bounded on ?Ω and if the balls B(r) are bounded, we characterize Markov uniqueness of H in terms of local capacity estimates and boundary capacity estimates. For example, H is Markov unique if and only if for each bounded subset A of ${\overline\Omega}$ there exist ${\eta_n \in C_c^\infty(\Omega)}$ satisfying , where ${\Gamma(\eta_n) = \sum^d_{k,l=1}c_{kl} (\partial_k \eta_n) (\partial_l \eta_n)}$ , and for each ${\varphi \in L_2(\Omega)}$ or if and only if cap(?Ω) = 0.     

Derived semidistributive lattices

For L a finite lattice, let ${\mathbb {C}(L) \subseteq L^2}$ denote the set of pairs γ = (γ ₀, γ ₁) such that ${\gamma_0 \prec \gamma_1}$ and order it as followsγ ≤ δ iff γ ₀ ≤ δ ₀, ${\gamma_{1} \nleq \delta_0,}$ and γ ₁ ≤ δ ₁. Let ${\mathbb {C}(L, \gamma)}$ denote the connected component of γ in this poset. Our main result states that, for any ${\gamma, \mathbb {C}(L, \gamma)}$ is a semidistributive lattice if L is semidistributive, and that ${\mathbb {C}(L, \gamma)}$ is a bounded lattice if L is bounded. Let ${\mathcal{S}_{n}}$ be the Permutohedron on n letters and let ${\mathcal{T}_{n}}$ be the Associahedron on n + 1 letters. Explicit computations show that ${\mathbb {C}(\mathcal{S}_{n}, \alpha) = \mathcal{S}_{n-1}}$ and ${\mathbb {C}(\mathcal {T}_n, \alpha) = \mathcal {T}_{n-1}}$ , up to isomorphism, whenever α1 is an atom of ${\mathcal{S}_{n}}$ or ${\mathcal{T}_{n}}$ . These results are consequences of new characterizations of finite join-semidistributive and of finite lower bounded lattices: (i) a finite lattice is join-semidistributive if and only if the projection sending ${\gamma \in \mathbb {C}(L)}$ to ${\gamma_0 \in L}$ creates pullbacks, (ii) a finite join-semidistributive lattice is lower bounded if and only if it has a strict facet labelling. Strict facet labellings, as defined here, are a generalization of the tools used by Caspard et al. to prove that lattices of finite Coxeter groups are bounded.     

Solvability of the Dirichlet problem for degenerate quasilinear elliptic equations

In a bounded domain of the n -dimensional (n?2) space one considers a class of degenerate quasilinear elliptic equations, whose model is the equation $$\sum\limits_{i = 1}^n {\frac{{\partial F}}{{\partial x_i }}} (a^{\ell _i } (u)\left| {u_{x_i } } \right|^{m_i - 2} u_{x_i } ) = f(x),$$ where x =(x₁,..., x_r), l_i?0, m_i>1, the function f is summable with some power, the nonnegative continuous function a(u) vanishes at a finite number of points and satisfies \(\frac{{lim}}{{\left| u \right| \to \infty }}a(u) > 0\) . One proves the existence of bounded generalized solutions with a finite integral $$\int\limits_\Omega {\sum\limits_{i = 1}^n {a^{\ell _i } (u)\left| {u_{x_i } } \right|^{m_i } dx} }$$ of the Dirichlet problem with zero boundary conditions.