Projection methods: an annotated bibliography of books and reviews

Projections onto sets are used in a wide variety of methods in optimization theory but not every method that uses projections really belongs to the class of projection methods as we mean it here. Here, projection methods are iterative algorithms that use projections onto sets while relying on the general principle that when a family of (usually closed and convex) sets is present, then projections (or approximate projections) onto the given individual sets are easier to perform than projections onto other sets (intersections, image sets under some transformation, etc.) that are derived from the given family of individual sets. Projection methods employ projections (or approximate projections) onto convex sets in various ways. They may use different kinds of projections and, sometimes, even use different projections within the same algorithm. They serve to solve a variety of problems which are either of the feasibility or the optimization types. They have different algorithmic structures, of which some are particularly suitable for parallel computing, and they demonstrate nice convergence properties and/or good initial behavioural patterns. This class of algorithms has witnessed great progress in recent years and its member algorithms have been applied with success to many scientific, technological and mathematical problems. This annotated bibliography includes books and review papers on, or related to, projection methods that we know about, use and like. If you know of books or review papers that should be added to this list please contact us.     

Grand Tour and Projection Pursuit

Abstract

The grand tour and projection pursuit are two methods for exploring multivariate data. We show how to combine them into a dynamic graphical tool for exploratory data analysis, called a projection pursuit guided tour. This tool assists in clustering data when clusters are oddly shaped and in finding general low-dimensional structure in high-dimensional, and in particular, sparse data. An example shows that the method, which is projection-based, can be quite powerful in situations that may cause grief for methods based on kernel smoothing. The projection pursuit guided tour is also useful for comparing and developing projection pursuit indexes and illustrating some types of asymptotic results.     

Influence analysis of non-Gaussianity by applying projection pursuit

The Gaussian distribution is the least structured from the information-theoretic point of view. In this paper, projection pursuit is used to find non-Gaussian projections to explore the clustering structure of the data. We use kurtosis as a measure of non-Gaussianity to find the projection directions. Kurtosis is well known to be sensitive to influential points/outliers, and so the projection direction will be greatly affected by unusual points. We also develop the influence functions of projection directions to investigate abnormal observations. A data example illustrates the application of these approaches.     

Subspaces,angles and pairs of orthogonal projections

We give a new proof for the Wedin theorem on the simultaneous unitary similarity transformation of two orthogonal projections and show that it is equivalent to Halmos' theorem on the unitary equivalence of projection pairs. As a consequence of these theorems, we derive several results on pairs of orthogonal projections, relative subspace positions and oblique projections as well.     

SUPERAPPROXIMATION PROPERTIES OF THE INTERPOLATION OPERATOR OF PROJECTION TYPE AND APPLICATIONS

AbstractSome superapproximation and ultra-approximation properties in function, gradient and two-order derivative approximations are shown for the interpolation operator of projection type on two-dimensional domain. Then, we consider the Ritz projection and Ritz-Volterra projection on finite element spaces, and by means of the superapproximation elementary estimates and Green function methods, derive the superconvergence and ultraconvergence error estimates for both projections, which are also the finite element approximation solutions of the elliptic problems and the Sobolev equations, respectively.     

Projection Pursuit for Exploratory Supervised Classification

In high-dimensional data, one often seeks a few interesting low-dimensional projections that reveal important features of the data. Projection pursuit is a procedure for searching high-dimensional data for interesting low-dimensional projections via the optimization of a criterion function called the projection pursuit index. Very few projection pursuit indices incorporate class or group information in the calculation. Hence, they cannot be adequately applied in supervised classification problems to provide low-dimensional projections revealing class differences in the data. This article introduces new indices derived from linear discriminant analysis that can be used for exploratory supervised classification.     

Zero weights and non-zero slacks: Different solutions to the same problem

This paper re-assesses three independently developed approaches that are aimed at solving the problem of zero-weights or non-zero slacks in Data Envelopment Analysis (DEA). The methods are weights restricted, non-radial and extended facet DEA models. Weights restricted DEA models are dual to envelopment DEA models with restrictions on the dual variables (DEA weights) aimed at avoiding zero values for those weights; non-radial DEA models are envelopment models which avoid non-zero slacks in the input-output constraints. Finally, extended facet DEA models recognize that only projections on facets of full dimension correspond to well defined rates of substitution/transformation between all inputs/outputs which in turn correspond to non-zero weights in the multiplier version of the DEA model. We demonstrate how these methods are equivalent, not only in their aim but also in the solutions they yield. In addition, we show that the aforementioned methods modify the production frontier by extending existing facets or creating unobserved facets. Further we propose a new approach that uses weight restrictions to extend existing facets. This approach has some advantages in computational terms, because extended facet models normally make use of mixed integer programming models, which are computationally demanding.     

Iterative algorithms for solving fixed point problems and variational inequalities with uniformly continuous monotone operators

Using the double projection and Halpern methods, we prove two strong convergence results for finding a solution of a variational inequality problem involving uniformly continuous monotone operator which is also a fixed point of a quasi-nonexpansive mapping in a real Hilbert space. In our proposed methods, only two projections onto the feasible set in each iteration are performed, rather than one projection for each tentative step during the Armijo-type search, which represents a considerable saving especially when the projection is computationally expensive. We also give some numerical results which show that our proposed algorithms are efficient and implementable from the numerical point of view.     

<Emphasis Type="Italic">G</Emphasis>-projectable and Λ-projectable binary linear block codes

The binary [24,12,8] Golay code has projection O onto the quaternary [6,3,4] hexacode [9] and the [32,16,8] Reed-Muller code has projection E onto the quaternary self-dual [8,4,4] code [6]. Projection E was extended to projection G in [8]. In this paper we introduce a projection, to be called projection Λ, that covers projections O, E and G. We characterise G-projectable self-dual codes and Λ-projectable codes. Explicit methods for constructing codes having G and Λ projections are given and several so constructed codes that have best known optimal parameters are introduced.      

Covariance-Guided Mixture Probabilistic Principal Component Analysis (C-MPPCA)

To extract information from high-dimensional data efficiently, visualization tools based on data projection methods have been developed and shown useful. However, a single two-dimensional visualization is often insufficient for capturing all or most interesting structures in complex high-dimensional datasets. For this reason, Tipping and Bishop developed mixture probabilistic principal component analysis (MPPCA) that separates data into multiple groups and enables a unique projection per group; that is, one probabilistic principal component analysis (PPCA) data visualization per group. Because the group labels are assigned to observations based on their high-dimensional coordinates, MPPCA works well to reveal homoscedastic structures in data that differ spatially. In the presence of heteroscedasticity, however, MPPCA may still mask noteworthy data structures. We propose a new method called covariance-guided MPPCA (C-MPPCA) that groups subsets of observations based on covariance, not locality, and, similar to MPPCA, displays them using PPCA. PPCA projects data in the dimensions with the highest variances, thus grouping by covariance makes sense and enables some data structures to be visible that were masked originally by MPPCA. We demonstrate the performance of C-MPPCA in an extensive simulation study. We also apply C-MPPCA to a real world dataset. Supplementary materials for this article are available online.     

Compact open sets in dual spaces and projections in group algebras of [FC]? groups

The structure of a compact open set in the dual of an [FC]^? group G, a locally compact group with relatively compact conjugacy classes, is given in terms of certain subsets which arise somewhat naturally. The support in the dual of a projection in L ¹(G) is a compact open set. Therefore, knowledge of the structure of such sets helps in identifying and constructing projections. We describe explicitly the compact open sets and construct projections for some illustrative examples.     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.     

Interpolatory model reduction of parameterized bilinear dynamical systems

Interpolatory projection methods for model reduction of nonparametric linear dynamical systems have been successfully extended to nonparametric bilinear dynamical systems. However, this has not yet occurred for parametric bilinear systems. In this work, we aim to close this gap by providing a natural extension of interpolatory projections to model reduction of parametric bilinear dynamical systems. We introduce necessary conditions that the projection subspaces must satisfy to obtain parametric tangential interpolation of each subsystem transfer function. These conditions also guarantee that the parameter sensitivities (Jacobian) of each subsystem transfer function are matched tangentially by those of the corresponding reduced-order model transfer function. Similarly, we obtain conditions for interpolating the parameter Hessian of the transfer function by including additional vectors in the projection subspaces. As in the parametric linear case, the basis construction for two-sided projections does not require computing the Jacobian or the Hessian.     

A new algorithm of non-Gaussian component analysis with radial kernel functions

We consider high-dimensional data which contains a linear low-dimensional non-Gaussian structure contaminated with Gaussian noise, and discuss a method to identify this non-Gaussian subspace. For this problem, we provided in our previous work a very general semi-parametric framework called non-Gaussian component analysis (NGCA). NGCA has a uniform probabilistic bound on the error of finding the non-Gaussian components and within this framework, we presented an efficient NGCA algorithm called Multi-index Projection Pursuit. The algorithm is justified as an extension of the ordinary projection pursuit (PP) methods and is shown to outperform PP particularly when the data has complicated non-Gaussian structure. However, it turns out that multi-index PP is not optimal in the context of NGCA. In this article, we therefore develop an alternative algorithm called iterative metric adaptation for radial kernel functions (IMAK), which is theoretically better justifiable within the NGCA framework. We demonstrate that the new algorithm tends to outperform existing methods through numerical examples.     

Alternative targets for data envelopment analysis through multi-objective linear programming: Rio de Janeiro Odontological Public Health System Case Study

In the last 10 years much has been written about the drawbacks of radial projection. During this time, many authors proposed methods to explore, interactively or not, the efficient frontier via non-radial projections. This paper compares three families of data envelopment analysis (DEA) models: the traditional radial, the preference structure and the multi-objective models. We use the efficiency analysis of Rio de Janeiro Odontological Public Health System as a background for comparing the three methods through a real case with one integer and one exogenous variable. The objectives of the study case are (i) to compare the applicability of the three approaches for efficiency analysis with exogenous and integer variables, (ii) to present the main advantages and drawbacks for each approach, (iii) to prove the impossibility to project in some regions and its implications, (iv) to present the approximate CPU time for the models, when this time is not negligible. We find that the multi-objective approach, although mathematically equivalent to its preference structure peer, allows projections that are not present in the latter. Furthermore, we find that, for our case study, the traditional radial projection model provides useless targets, as expected. Furthermore, for some parts of the frontier, none of the models provide suitable targets. Other interesting result is that the CPU-time for the multi-objective formulation, although its endogenous high complexity, is acceptable for DEA applications, due to its compact nature.     

Signal enhancement and the method of successive projections

The signal enhancement algorithm of Cadzow is developed in the context of best approximation theory and Combettes' method of successive projections, which is a generalization of the method of projection on convex sets. The relevant mathematical methods are surveyed. Applications of the signal enhancement algorithm to direction-of-arrival array signal processing for narrow-band and wide-band sources, data interpolation, signal detection, and x-ray fluorescence spectrum processing are presented.     

Nonlinear Ergodic Theorem for Positively Homogeneous Nonexpansive Mappings in Banach Spaces

Recently, two retractions (projections), which are different from the metric projection and the sunny nonexpansive retraction in a Banach space, were found. In this article, using nonlinear analytic methods and new retractions, we prove a nonlinear ergodic theorem for positively homogeneous and nonexpansive mappings in a uniformly convex Banach space. The limit points are characterized by using new retractions.     

Oracle convergence rate of posterior under projection prior and Bayesian model selection

We apply the Bayes approach to the problem of projection estimation of a signal observed in the Gaussian white noise model and we study the rate at which the posterior distribution concentrates about the true signal from the space ℓ₂ as the information in observations tends to infinity. A benchmark is the rate of a so-called oracle projection risk, i.e., the smallest risk of an unknown true signal over all projection estimators. Under an appropriate hierarchical prior, we study the performance of the resulting (appropriately adjusted by the empirical Bayes approach) posterior distribution and establish that the posterior concentrates about the true signal with the oracle projection convergence rate. We also construct a Bayes estimator based on the posterior and show that it satisfies an oracle inequality. The results are nonasymptotic and uniform over ℓ₂. Another important feature of our approach is that our results on the oracle projection posterior rate are always stronger than any result about posterior convergence with the minimax rate over all nonparametric classes for which the corresponding projection oracle estimator is minimax over this class. We also study implications for the model selection problem, namely, we propose a Bayes model selector and assess its quality in terms of the so-called false selection probability.     

Approximation Spaces in the Numerical Analysis of Operator Equations

We show that generalized approximation spaces can be used to prove stability and convergence of projection methods for certain types of operator equations in which unbounded operators occur. Besides the convergence, we also get orders of convergence by this approach, even in case of non-uniformly bounded projections. We give an example in which weighted uniform convergence of the collocation method for an easy Cauchy singular integral equation is studied.     

Projection methods for computing Moore-Penrose inverses of unbounded operators

In this article we give a characterization of the convergence of projection methods which are useful for approximating the Moore-Penrose inverse of a closed densely defined operator between Hilbert spaces. We illustrate the main theorem with an example. Also a procedure for constructing the admissible sequence of projections is discussed.