Accelerating the convergence of the method of alternating projections

The powerful von Neumann-Halperin method of alternating projections (MAP) is an algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces. It achieves this by reducing the problem to an iterative scheme which involves only computing best approximations from the individual subspaces which make up the intersection. The main practical drawback of this algorithm, at least for some applications, is that the method is slowly convergent. In this paper, we consider a general class of iterative methods which includes the MAP as a special case. For such methods, we study an ``accelerated' version of this algorithm that was considered earlier by Gubin, Polyak, and Raik (1967) and by Gearhart and Koshy (1989). We show that the accelerated algorithm converges faster than the MAP in the case of two subspaces, but is, in general, not faster than the MAP for more than two subspaces! However, for a ``symmetric' version of the MAP, the accelerated algorithm always converges faster for any number of subspaces. Our proof seems to require the use of the Spectral Theorem for selfadjoint mappings.

     

A sharp convergence estimate for the method of subspace corrections for singular systems of equations

This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.

     

A generalization of the Friedrichs angle and the method of alternating projections

We present a generalization to an arbitrary number of subspaces of the cosine of the Friedrichs angle between two subspaces of a Hilbert space. This parameter is used to analyze the rate of convergence in the von Neumann–Halperin method of alternating projections.     

Optimal Non-Linear Models for Sparsity and Sampling

Given a set of vectors (the data) in a Hilbert space ?, we prove the existence of an optimal collection of subspaces minimizing the sum of the square of the distances between each vector and its closest subspace in the collection. This collection of subspaces gives the best sparse representation for the given data, in a sense defined in the paper, and provides an optimal model for sampling in union of subspaces. The results are proved in a general setting and then applied to the case of low dimensional subspaces of ? ^N and to infinite dimensional shift-invariant spaces in L ²(? ^d ). We also present an iterative search algorithm for finding the solution subspaces. These results are tightly connected to the new emergent theories of compressed sensing and dictionary design, signal models for signals with finite rate of innovation, and the subspace segmentation problem.     

Convergence of minimum norm elements of projections and intersections of nested affine spaces in Hilbert space

We consider a Hilbert space, an orthogonal projection onto a closed subspace and a sequence of downwardly directed affine spaces. We give sufficient conditions for the projection of the intersection of the affine spaces into the closed subspace to be equal to the intersection of their projections. Under a closure assumption, one such (necessary and) sufficient condition is that summation and intersection commute between the orthogonal complement of the closed subspace, and the subspaces corresponding to the affine spaces. Another sufficient condition is that the cosines of the angles between the orthogonal complement of the closed subspace, and the subspaces corresponding to the affine spaces, be bounded away from one. Our results are then applied to a general infinite horizon, positive semi-definite, linear quadratic mathematical programming problem. Specifically, under suitable conditions, we show that optimal solutions exist and, modulo those feasible solutions with zero objective value, they are limits of optimal solutions to finite-dimensional truncations of the original problem.     

A contraction proximal point algorithm with two monotone operators

It is a known fact that the method of alternating projections introduced long ago by von Neumann fails to converge strongly for two arbitrary nonempty, closed and convex subsets of a real Hilbert space. In this paper, a new iterative process for finding common zeros of two maximal monotone operators is introduced and strong convergence results associated with it are proved. If the two operators are subdifferentials of indicator functions, this new algorithm coincides with the old method of alternating projections. Several other important algorithms, such as the contraction proximal point algorithm, occur as special cases of our algorithm. Hence our main results generalize and unify many results that occur in the literature.     

Sparse fusion frames: existence and construction

Fusion frame theory is an emerging mathematical theory that provides a natural framework for performing hierarchical data processing. A fusion frame can be regarded as a frame-like collection of subspaces in a Hilbert space, and thereby generalizes the concept of a frame for signal representation. However, when the signal and/or subspace dimensions are large, the decomposition of the signal into its fusion frame measurements through subspace projections typically requires a large number of additions and multiplications, and this makes the decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we introduce the notion of a sparse fusion frame, that is, a fusion frame whose subspaces are generated by orthonormal basis vectors that are sparse in a ‘uniform basis’ over all subspaces, thereby enabling low-complexity fusion frame decompositions. We study the existence and construction of sparse fusion frames, but our focus is on developing simple algorithmic constructions that can easily be adopted in practice to produce sparse fusion frames with desired (given) operators. By a desired (or given) operator we simply mean one that has a desired (or given) set of eigenvalues for the fusion frame operator. We start by presenting a complete characterization of Parseval fusion frames in terms of the existence of special isometries defined on an encompassing Hilbert space. We then introduce two general methodologies to generate new fusion frames from existing ones, namely the Spatial Complement Method and the Naimark Complement Method, and analyze the relationship between the parameters of the original and the new fusion frame. We proceed by establishing existence conditions for 2-sparse fusion frames for any given fusion frame operator, for which the eigenvalues are greater than or equal to two. We then provide an easily implementable algorithm for computing such 2-sparse fusion frames.     

The numerical range and the spectrum of a product of two orthogonal projections

The aim of this paper is to describe the closure of the numerical range of the product of two orthogonal projections in Hilbert space as a closed convex hull of some explicit ellipses parametrized by points in the spectrum. Several improvements (removing the closure of the numerical range of the operator, using a parametrization after its eigenvalues) are possible under additional assumptions. An estimate of the least angular opening of a sector with vertex 1 containing the numerical range of a product of two orthogonal projections onto two subspaces is given in terms of the cosine of the Friedrichs angle. Applications to the rate of convergence in the method of alternating projections and to the uncertainty principle in harmonic analysis are also discussed.     

A relaxed self-adaptive CQ algorithm for the multiple-sets split feasibility problem

The multiple-sets split feasibility problem (MSFP) is to find a point belongs to the intersection of a family of closed convex sets in one space, such that its image under a linear transformation belongs to the intersection of another family of closed convex sets in the image space. Many iterative methods can be employed to solve the MSFP. Jinling Zhao et al. proposed a modification for the CQ algorithm and a relaxation scheme for this modification to solve the MSFP. The strong convergence of these algorithms are guaranteed in finite-dimensional Hilbert spaces. Recently López et al. proposed a relaxed CQ algorithm for solving split feasibility problem, this algorithm can be implemented easily since it computes projections onto half-spaces and has no need to know a priori the norm of the bounded linear operator. However, this algorithm has only weak convergence in the setting of infinite-dimensional Hilbert spaces. In this paper, we introduce a new relaxed self-adaptive CQ algorithm for solving the MSFP where closed convex sets are level sets of some convex functions such that the strong convergence is guaranteed in the framework of infinite-dimensional Hilbert spaces. Our result extends and improves the corresponding results.     

A von Neumann alternating method for finding common solutions to variational inequalities

By modifying von Neumann’s alternating projections algorithm, we obtain an alternating method for solving the recently introduced Common Solutions to Variational Inequalities Problem (CSVIP). For simplicity, we mainly confine our attention to the two-set CSVIP, which entails finding common solutions to two unrelated variational inequalities in Hilbert space.     

基于Kernel Discriminant Canonical Correlation(KDCC)的多观测样本分类算法

针对多观测样本分类问题,提出一种基于Kernel Discriminant CanonicalCorrelation(KDCC)来实现多观测样本分类的模型.该算法首先把原空间样本非线性的投影到高维特征空间,通过KPCA得到核子空间,然后在高维特征空间定义一个使类内核子空间的相关性最大,同时使类间核子空间的相关性最小的KDCC矩阵,通过迭代法训练出最优的KDCC矩阵,把每个核子空间投影到KDCC矩阵上得到转换核子空间,采用典型相关性作为转换核子空间之间的相似性度量,并采用最近邻准则作为多观测样本的分类决策,从而实现多观测样本的分类.在三个数据库上进行了一系列实验,实验结果表明提出的方法对于多观测样本分类具有可行性和有效性.     

A finite steps algorithm for solving convex feasibility problems

This paper develops a new variant of the classical alternating projection method for solving convex feasibility problems where the constraints are given by the intersection of two convex cones in a Hilbert space. An extension to the feasibility problem for the intersection of two convex sets is presented as well. It is shown that one can solve such problems in a finite number of steps and an explicit upper bound for the required number of steps is obtained. As an application, we propose a new finite steps algorithm for linear programming with linear matrix inequality constraints. This solution is computed by solving a sequence of a matrix eigenvalue decompositions. Moreover, the proposed procedure takes advantage of the structure of the problem. In particular, it is well adapted for problems with several small size constraints.     

On the Borelness of the intersection operation

We study the intersection operation of closed linear subspaces in a separable Banach space. We show that if the ambient space is quasi-reflexive, then the intersection operation is Borel. On the other hand, if the space contains a closed subspace with a Schauder decomposition into infinitely many non-reflexive spaces, then the intersection operation is not Borel. As a corollary, for a closed subspace of a Banach space with an unconditional basis, the intersection operation of the closed linear subspaces is Borel if and only if the space is reflexive. We also consider the intersection operation of additive subgroups in an infinite-dimensional separable Banach space, and show that if this intersection operation is Borel then the space is hereditarily indecomposable.     

两子空间的公共补与Groβ问题

设U,V是Hilbert空间H的两个闭子空间．若存在H的闭子空间L满足L+U=H,L+V=H,且L∩U=L∩V={0},则称L是U和V的公共补．本文获得了两子空间有公共补的一些新的特征,给出了等式H=[U∩(U⊥+ V⊥)]⊕[V⊕(U⊥∩V⊥)]成立的充分必要条件,完全回答了GroB提出的问题．     

Aveiro method in reproducing kernel Hilbert spaces under complete dictionary

Aveiro method is a sparse representation method in reproducing kernel Hilbert spaces, which gives orthogonal projections in linear combinations of reproducing kernels over uniqueness sets. It, however, suffers from determination of uniqueness sets in the underlying reproducing kernel Hilbert space. In fact, in general spaces, uniqueness sets are not easy to be identified, let alone the convergence speed aspect with Aveiro method. To avoid those difficulties, we propose an new Aveiro method based on a dictionary and the matching pursuit idea. What we do, in fact, are more: The new Aveiro method will be in relation to the recently proposed, the so‐called pre‐orthogonal greedy algorithm involving completion of a given dictionary. The new method is called Aveiro method under complete dictionary. The complete dictionary consists of all directional derivatives of the underlying reproducing kernels. We show that, under the boundary vanishing condition bring available for the classical Hardy and Paley‐Wiener spaces, the complete dictionary enables an efficient expansion of any given element in the Hilbert space. The proposed method reveals new and advanced aspects in both the Aveiro method and the greedy algorithm.     

次可分解算子的不变子空间格的丰富性

证明了一类次可分解算子的不变子空间格是丰富的,并举例说明存在Hilbert空间上的有界线性算子T,它有无穷多个不变子空间,但是它的不变子空间格Lat(T)不丰富．     

Steepest‐descent proximal point algorithms for a class of variational inequalities in Banach spaces

In this paper, we present a new approach to the problem of finding a common zero for a system of m‐accretive mappings in a uniformly convex Banach space with a uniformly Gâteaux differentiable norm. We propose an implicit iteration method and two explicit ones, based on compositions of resolvents with the steepest‐descent method. We show that our results contain some iterative methods in literature as special cases. An extension of the Xu's regularization method for the proximal point algorithm from Hilbert spaces onto Banach ones under simple conditions of convergence and a new variant for the method of alternating resolvents are obtained. Numerical experiments are given to affirm efficiency of the methods.     

On the properties of orthorecursive expansions with respect to subspaces

In a Hilbert space, for orthorecursive expansions with respect to closed subspaces, we establish a criterion for expansions of elements of a certain finite-dimensional subspace with respect to a finite sequence of subspaces to coincide with the expanded elements. This implies a criterion for an element to be equal to its orthorecursive expansion with respect to a finite sequence of subspaces. We also obtain a number of results related to the best approximations of elements by partial sums of their orthorecursive expansions with respect to a sequence of finite-dimensional subspaces.     

Finding projections onto the intersection of convex sets in Hilbert spaces. II

We present a parallel iterative algorithm to find the shortest distance projection of a given point onto the intersection of a finite number of closed convex sets in a real Hilbert space; the number of sets used at each iteration step, corresponding to the number of available processors, may be smaller than the total number of sets. The relaxation coefficient at each iteraction step is determined by a geometric condition in an associated Hilbert space, while for the weights mild conditions are given to assure norm convergence of the resulting sequence. These mild conditions leave enough flexibility to determine the weights more specifically in order to improve the speed of convergence.     

An alternating projections method for certain linear problems in a Hilbert space

Recent extensions of von Neumann's alternating projection methodpermit the computation of proximity projections onto certainconvex sets. This paper exploits this fact in constructing aglobally convergent method for minimizing linear functions overa convex set in a Hilbert space. In particular, we solve theeducational testing problem and an inverse eigenvalue problem,two difficult problems involving positive semidefiniteness constraints.