Character formulas for Feigin–Stoyanovsky’s type subspaces of standard $\mathfrak{sl}(3, \mathbb{C})^{\widetilde{}}$-modules

Exact sequences of Feigin–Stoyanovsky’s type subspaces for affine Lie algebra \mathfraksl(l+1,\mathbbC)^[\tilde]\mathfrak{sl}(l+1,\mathbb{C})^{\widetilde{}} lead to systems of recurrence relations for formal characters of those subspaces. By solving the corresponding system for \mathfraksl(3,\mathbbC)^[\tilde]\mathfrak{sl}(3,\mathbb{C})^{\widetilde{}}, we obtain a new family of character formulas for all Feigin–Stoyanovsky’s type subspaces at the general level.     

Convergence analysis of a conforming adaptive finite element method for an obstacle problem

The adaptive algorithm for the obstacle problem presented in this paper relies on the jump residual contributions of a standard explicit residual-based a posteriori error estimator. Each cycle of the adaptive loop consists of the steps ‘SOLVE’, ‘ESTIMATE’, ‘MARK’, and ‘REFINE’. The techniques from the unrestricted variational problem are modified for the convergence analysis to overcome the lack of Galerkin orthogonality. We establish R-linear convergence of the part of the energy above its minimal value, if there is appropriate control of the data oscillations. Surprisingly, the adaptive mesh-refinement algorithm is the same as in the unconstrained case of a linear PDE—in fact, there is no modification near the discrete free boundary necessary for R-linear convergence. The arguments are presented for a model obstacle problem with an affine obstacle χ and homogeneous Dirichlet boundary conditions. The proof of the discrete local efficiency is more involved than in the unconstrained case. Numerical results are given to illustrate the performance of the error estimator.     

Functions with prescribed best linear approximations

A common problem in applied mathematics is that of finding a function in a Hilbert space with prescribed best approximations from a finite number of closed vector subspaces. In the present paper we study the question of the existence of solutions to such problems. A finite family of subspaces is said to satisfy the Inverse Best Approximation Property (IBAP) if there exists a point that admits any selection of points from these subspaces as best approximations. We provide various characterizations of the IBAP in terms of the geometry of the subspaces. Connections between the IBAP and the linear convergence rate of the periodic projection algorithm for solving the underlying affine feasibility problem are also established. The results are applied to investigate problems in harmonic analysis, integral equations, signal theory, and wavelet frames.     

Fast computation of spectral centroids

The spectral centroid of a signal is the curve whose value at any given time is the centroid of the corresponding constant-time cross section of the signal’s spectrogram. A spectral centroid provides a noise-robust estimate of how the dominant frequency of a signal changes over time. As such, spectral centroids are an increasingly popular tool in several signal processing applications, such as speech processing. We provide a new, fast and accurate algorithm for the real-time computation of the spectral centroid of a discrete-time signal. In particular, by exploiting discrete Fourier transforms, we show how one can compute the spectral centroid of a signal without ever needing to explicitly compute the signal’s spectrogram. We then apply spectral centroids to an emerging biometrics problem: to determine a person’s heart and breath rates by measuring the Doppler shifts their body movements induce in a continuous wave radar signal. We apply our algorithm to real-world radar data, obtaining heart- and breath-rate estimates that compare well against ground truth.     

Deriving Karmarkar’s LP algorithm using angular projection matrix

Understanding Karmarkar’s algorithm is both desirable and necessary for its efficient implementation, for further improvement and for carrying out complexity analysis. In this report an algorithm based on the concept of angular projection matrix, to solve linear programming problems is derived. Surprisingly, this algorithm coincides with the affine version of Karmarkar’s algorithm.     

Spectral Radius Algebras of Idempotents

We show that the spectral radius algebras of certain quadratic operators possess nontrivial invariant subspaces. Additionally, such algebras properly contain the operator’s commutant, so that the invariant subspaces are in some sense beyond hyperinvariant. The spectral radius algebras of idempotents are completely described and, as a consequence, it is shown that every intransitive collection of operators must be contained in a norm-closed proper spectral radius algebra.      

Clustering Rules: A Comparison of Partitioning and Hierarchical Clustering Algorithms

Previous research has resulted in a number of different algorithms for rule discovery. Two approaches discussed here, the ‘all-rules’ algorithm and multi-objective metaheuristics, both result in the production of a large number of partial classification rules, or ‘nuggets’, for describing different subsets of the records in the class of interest. This paper describes the application of a number of different clustering algorithms to these rules, in order to identify similar rules and to better understand the data.     

A Global Optimization RLT-based Approach for Solving the Hard Clustering Problem

The field of cluster analysis is primarily concerned with the sorting of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the hard clustering problem, where each data point is to be assigned to exactly one cluster. The hard clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities that serve to defeat the inherent symmetry in the problem. This construct is embedded within a specialized branch-and-bound algorithm to solve the problem to global optimality. Pertinent implementation issues that can enhance the efficiency of the branch-and-bound algorithm are also discussed. Computational experience is reported using several standard data sets found in the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular k-means clustering technique. Finally, a heuristic procedure to obtain a good quality solution at a relative ease of computational effort is also described.     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

Consistency of regularized spectral clustering

Clustering is a widely used technique in machine learning, however, relatively little research in consistency of clustering algorithms has been done so far. In this paper we investigate the consistency of the regularized spectral clustering algorithm, which has been proposed recently. It provides a natural out-of-sample extension for spectral clustering. The presence of the regularization term makes our situation different from that in previous work. Our approach is mainly an elaborate analysis of a functional named the clustering objective. Moreover, we establish a convergence rate. The rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual.     

Beurling Dimension of Gabor Pseudoframes for Affine Subspaces

Pseudoframes for subspaces have been recently introduced by Li and Ogawa as a tool to analyze lower dimensional data with arbitrary flexibility of both the analyzing and the dual sequence. In this paper we study Gabor pseudoframes for affine subspaces by focusing on geometrical properties of their associated sets of parameters. We first introduce a new notion of Beurling dimension for discrete subsets of ℝ ^d by employing a certain generalized Beurling density. We present several properties of Beurling dimension including a comparison with other notions of dimension showing, for instance, that our notion includes the mass dimension as a special case. Then we prove that Gabor pseudoframes for affine subspaces satisfy a certain Homogeneous Approximation Property, which implies invariance under time–frequency shifts of an approximation by elements from the pseudoframe. The main result of this paper is a classification of Gabor pseudoframes for affine subspaces by means of the Beurling dimension of their sets of parameters. This provides us, in particular, with a Nyquist dimension which separates sets of parameters of pseudoframes from those of non-pseudoframes and which links a fixed value to sets of parameters of pseudo-Riesz sequences. These results are even new for the special case of Gabor frames for an affine subspace.      

On the linear convergence of the circumcentered-reflection method

In order to accelerate the Douglas–Rachford method we recently developed the circumcentered-reflection method, which provides the closest iterate to the solution among all points relying on successive reflections, for the best approximation problem related to two affine subspaces. We now prove that this is still the case when considering a family of finitely many affine subspaces. This property yields linear convergence and incites embedding of circumcenters within classical reflection and projection based methods for more general feasibility problems.     

Splitting Methods for Convex Clustering

Clustering is a fundamental problem in many scientific applications. Standard methods such as k-means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of k-means and hierarchical clustering shrink cluster centroids toward one another and ensure a unique global minimizer. In this work, we present two splitting methods for solving the convex clustering problem. The first is an instance of the alternating direction method of multipliers (ADMM); the second is an instance of the alternating minimization algorithm (AMA). In contrast to previously considered algorithms, our ADMM and AMA formulations provide simple and unified frameworks for solving the convex clustering problem under the previously studied norms and open the door to potentially novel norms. We demonstrate the performance of our algorithm on both simulated and real data examples. While the differences between the two algorithms appear to be minor on the surface, complexity analysis and numerical experiments show AMA to be significantly more efficient. This article has supplementary materials available online.     

Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem

The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝ ^d , incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ ⁴/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n ^Δ+1 dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space. An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006. Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology. Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in part by NSF grant CCF-0346991. Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation.     

Evolutionary Monte Carlo Methods for Clustering

The problem of clustering a group of observations according to some objective function (e.g., K-means clustering, variable selection) or a density (e.g., posterior from a Dirichlet process mixture model prior) can be cast in the framework of Monte Carlo sampling for cluster indicators. We propose a new method called the evolutionary Monte Carlo clustering (EMCC) algorithm, in which three new “crossover moves,” based on swapping and reshuffling sub cluster intersections, are proposed. We apply the EMCC algorithm to several clustering problems including Bernoulli clustering, biological sequence motif clustering, BIC based variable selection, and mixture of normals clustering. We compare EMCC's performance both as a sampler and as a stochastic optimizer with Gibbs sampling, “split-merge” Metropolis–Hastings algorithms, K-means clustering, and the MCLUST algorithm.     

一种基于区间数多指标信息的FCM聚类算法

针对一类具有不确定性区间数多指标信息的聚类分析问题，依据传统的基于数值信息的FCM聚类算法的思路，提出了一种新的聚类分析算法。章首先描述了具有区间数多指标信息的聚类分析问题；其次给出了基于区间数多指标信息的关于最优划分和最优聚类中心确定的两个定理；然后给出了基于区间数多指标信息的FCM聚类算法的计算步骤。该算法的特点是聚类中心的表现形式为精确的数值，给出的两个定理说明了该聚类算法的收敛性。最后，通过给出一个算例说明了本给出的聚类算法。     

Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones

This paper presents an extension of the variant of Mehrotra’s predictor–corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646–658, 2006) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra’s original predictor–corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov–Todd direction, we show that the iteration-complexity bound of the proposed algorithm is , where r is the rank of the associated Euclidean Jordan algebras and ε>0 is the required precision.     

Model-based clustering of time series in group-specific functional subspaces

This work develops a general procedure for clustering functional data which adapts the clustering method high dimensional data clustering (HDDC), originally proposed in the multivariate context. The resulting clustering method, called funHDDC, is based on a functional latent mixture model which fits the functional data in group-specific functional subspaces. By constraining model parameters within and between groups, a family of parsimonious models is exhibited which allow to fit onto various situations. An estimation procedure based on the EM algorithm is proposed for determining both the model parameters and the group-specific functional subspaces. Experiments on real-world datasets show that the proposed approach performs better or similarly than classical two-step clustering methods while providing useful interpretations of the groups and avoiding the uneasy choice of the discretization technique. In particular, funHDDC appears to always outperform HDDC applied on spline coefficients.     

A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

Spectrum-Based Comparison of Stationary Multivariate Time Series

The problem of comparison of several multivariate time series via their spectral properties is discussed. A pairwise comparison between two independent multivariate stationary time series via a likelihood ratio test based on the estimated cross-spectra of the series yields a quasi-distance between the series. A hierarchical clustering algorithm is then employed to compare several time series given the quasi-distance matrix. For use in situations where components of the multivariate time series are measured in different units of scale, a modified quasi-distance based on a profile likelihood based estimation of the scale parameter is described. The approach is illustrated using simulated data and data on daily temperatures and precipitations at multiple locations. A comparison between hierarchical clustering based on the likelihood ratio test quasi-distance and a quasi-distance described in Kakizawa et al. (J Am Stat Assoc 93:328–340, 1998) is interesting.