In many domains, there is significant interest in capturing novel relationships between time series that represent activities recorded at different nodes of a highly complex system. In this paper, we introduce multipoles, a novel class of linear relationships between more than two time series. A multipole is a set of time series that have strong linear dependence among themselves, with the requirement that each time series makes a significant contribution to the linear dependence. We demonstrate that most interesting multipoles can be identified as cliques of negative correlations in a correlation network. Such cliques are typically rare in a real-world correlation network, which allows us to find almost all multipoles efficiently using a clique-enumeration approach. Using our proposed framework, we demonstrate the utility of multipoles in discovering new physical phenomena in two scientific domains: climate science and neuroscience. In particular, we discovered several multipole relationships that are reproducible in multiple other independent datasets and lead to novel domain insights.

Estimating the inverse covariance matrix of p variables from n observations is challenging when n is much less than p, since the sample covariance matrix is singular and cannot be inverted. A popular solution is to optimize for the L1 penalized estimator; however, this does not incorporate structure domain knowledge and can be expensive to optimize. We consider finding inverse covariance matrices with group structure, defined as potentially overlapping principal submatrices, determined from domain knowledge (e.g. categories or graph cliques). We propose a new estimator for this problem setting that can be derived efficiently via the conditional gradient method, leveraging chordal decomposition theory for scalability. Simulation results show significant improvement in sample complexity when the correct group structure is known. We also apply these estimators to 14,910 stock closing prices, with noticeable improvement when group sparsity is exploited.

Sparse models have proven to be extremely successful in image processing and computer vision. However, a majority of the effort has been focused on sparse representation of vectors and low-rank models for general matrices. The success of sparse modeling, along with popularity of region covariances, has inspired the development of sparse coding approaches for these positive definite descriptors. While in earlier work, the dictionary was formed from all, or a random subset of, the training signals, it is clearly advantageous to learn a concise dictionary from the entire training set. In this paper, we propose a novel approach for dictionary learning over positive definite matrices. The dictionary is learned by alternating minimization between sparse coding and dictionary update stages, and different atom update methods are described. A discriminative version of the dictionary learning approach is also proposed, which simultaneously learns dictionaries for different classes in classification or clustering. Experimental results demonstrate the advantage of learning dictionaries from data both from reconstruction and classification viewpoints. Finally, a software library is presented comprising C++ binaries for all the positive definite sparse coding and dictionary learning approaches presented here.

In recent years, there has been extensive research on sparse representation of vector-valued signals. In the matrix case, the data points are merely vectorized and treated as vectors thereafter (for example, image patches). However, this approach cannot be used for all matrices, as it may destroy the inherent structure of the data. Symmetric positive definite (SPD) matrices constitute one such class of signals, where their implicit structure of positive eigenvalues is lost upon vectorization. This paper proposes a novel sparse coding technique for positive definite matrices, which respects the structure of the Riemannian manifold and preserves the positivity of their eigenvalues, without resorting to vectorization. Synthetic and real-world computer vision experiments with region covariance descriptors demonstrate the need for and the applicability of the new sparse coding model. This work serves to bridge the gap between the sparse modeling paradigm and the space of positive definite matrices.

As a crucial operation, routing plays an important role in various communication networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based (“all-path”) routing have been developed. Existing results in the literature show that the shortest path and all-path routing can be obtained from$L_{1}$and$L_{2}$flow optimization, respectively. Based on this connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted)$L_{1}/L_{2}$-norms. We obtain a surprising result: as we vary the trade-off parameter$\theta$, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing—this entire sequence of routing graphs is referred to as the routing continuum. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering, wireless sensor networks, and network robustness analysis.

While Bregman divergences have been used for clustering and embedding problems in recent years, the facts that they are asymmetric and do not satisfy triangle inequality have been a major concern. In this paper, we investigate the relationship between two families of symmetrized Bregman divergences and metrics that satisfy the triangle inequality. The first family can be derived from any well-behaved convex function. The second family generalizes the Jensen-Shannon divergence, and can only be derived from convex functions with certain conditional positive definiteness structure. We interpret the required structure in terms of cumulants of infinitely divisible distributions, and related results in harmonic analysis. We investigate kmeans-type clustering problems using both families of symmetrized divergences, and give efficient algorithms for the same.

Constrained spectral clustering is a semi-supervised learning problem that aims at incorporating user-defined constraints in spectral clustering. Typically, there are two kinds of constraints: (i) must-link, and (ii) cannot-link. These constraints represent prior knowledge indicating whether two data objects should be in the same cluster or not; thereby aiding in clustering. In this paper, we propose a novel approach that uses convex subproblems to incorporate constraints in spectral clustering and co-clustering. In comparison to the prior state-of-art approaches, our approach presents a more natural way to incorporate constraints in the spectral methods and allows us to make a trade off between the number of satisfied constraints and the quality of partitions on the original graph. We use an L1 regularizer analogous to LASSO, often used in literature to induce sparsity, in order to control the number of constraints satisfied. Our approach can handle both must-link and cannot-link constraints, unlike a large number of previous approaches that mainly work on the former. Further, our formulation is based on the reduction to a convex subproblem which is relatively easy to solve using existing solvers. We test our proposed approach on real world datasets and show its effectiveness for both spectral clustering and co-clustering over the prior state-of-art.

Sparse models have proven to be extremely successful in image processing and computer vision, and most efforts have been focused on sparse representation of vectors. The success of sparse modeling and the popularity of region covariances have inspired the development of sparse coding approaches for positive definite matrices. While in earlier work [1], the dictionary was pre-determined, it is clearly advantageous to learn a concise dictionary adaptively from the data at hand. In this paper, we propose a novel approach for dictionary learning over positive definite matrices. The dictionary is learned by alternating minimization between the sparse coding and dictionary update stages, and two different atom update methods are described. The online versions of the dictionary update techniques are also outlined. Experimental results demonstrate that the proposed learning methods yield better dictionaries for positive definite sparse coding. The learned dictionaries are applied to texture and face data, leading to improved classification accuracy and strong detection performance, respectively.

Routing is a critical operation in networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based ("all-path") routing have been developed. Based on the connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted) L1/L2-norms. We obtain a surprising result: as we vary the trade-off parameter, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing - this entire sequence of routing graphs is referred to as the routing continuum. Our theory subsumes the earlier results showing the shortest path and all-path routing can be obtained from L1 and L2 flow optimization, respectively. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering and wireless sensor networks.

We consider the problem of finding a suitable common low dimensional subspace for accurately representing a given set of covariance matrices. With one covariance matrix, this is principal component analysis (PCA). For multiple covariance matrices, we term the problem Common Component Analysis (CCA). While CCA can be posed as a tensor decomposition problem, standard approaches to tensor decompositions have two critical issues: (i) tensor decomposition methods are iterative and rely on the initialization; (ii) for a given level of approximation error, it is difficult to choose a suitable low dimensionality. In this paper, we present a detailed analysis of CCA that yields an effective initialization and iterative algorithms for the problem. The proposed methodology has provable approximation guarantees w.r.t. the global maximum and also allows one to choose the dimensionality for a given level of approximation error. We also establish conditions under which the methodology will achieve the global maximum. We illustrate the effectiveness of the proposed method through extensive experiments on synthetic data as well as on two real stock market datasets, where major financial events can be visualized in low dimensions.

A scalable method to cluster data sets too large to fit in memory is presented. This method does not depend on random subsampling, but does scan every individual data sample in a deterministic way. The original data are represented in factored form by the product of two matrices, one or both of which is very sparse. This factored form avoids the need to multiply together these two matrices by using a variant of the Principal Direction Divisive Partitioning (PDDP) algorithm which does not depend on computing the distances between the individual samples. The resulting clustering algorithm is Piecemeal PDDP (PMPDDP), in which the original data are broken up into sections which will fit into memory and clustered. The cluster centers are used to create approximations to the original data items, and each original data item is represented by a linear combination of these centers. We evaluate the performance of PMPDDP on three real data sets, and observe that the quality of the clusters of PMPDDP is comparable to PDDP for the data sets examined.

We study a class of algorithms that speed up the training process of support vector machines (SVMs) by returning an approximate SVM. We focus on algorithms that reduce the size of the optimization problem by extracting from the original training dataset a small number of representatives and using these representatives to train an approximate SVM. The main contribution of this paper is a PAC-style generalization bound for the resulting approximate SVM, which provides a learning theoretic justification for using the approximate SVM in practice. The proved bound also generalizes and includes as a special case the generalization bound for the exact SVM, which denotes the SVM given by the original training dataset in this paper.

We address the problem of human motion recognition in this paper. The goal of human motion recognition is to recognize the type of motion recorded in a video clip, which consists of a set of temporarily ordered frames. By defining a Mercer kernel between two video clips directly, we propose in this paper a recognition strategy that can incorporate both the information of each individual frame and the temporal ordering between frames. Combining the proposed kernel with the support vector machine, which is one of the most effective classification paradigms, the resulting recognition strategy exhibits excellent performance over real data sets

We propose to speed up the training process of support vector machines (SVM) by resorting to an approximate SVM, where a small number of representatives are extracted from the original training data set and used for training. Theoretical studies show that, in order for the approximate SVM to be similar to the exact SVM given by the original training data set, kernel k-means should be used to extract the representatives. As practical variations, we also propose two efficient implementations of the proposed algorithm, where approximations to kernel k-means are used. The proposed algorithms are compared against the standard training algorithm over real data sets.

We propose a motion recognition strategy that represents a videoclip as a set of filtered images, each of which encodes a short period of motion history. Given a set of videoclips whose motion types are known, a filtered image classifier is built using support vector machines. In offline classification, the label of a test videoclip is obtained by applying majority voting over its filtered images. In online classification, the most probable type of action at an instance is determined by applying the majority voting over the most recent filtered images, which are within a sliding window. The effectiveness of this strategy was demonstrated on real datasets where the videoclips were recorded using a fixed camera whose optical axis is perpendicular to the person's trajectory. In offline recognition, the proposed strategy outperforms a principal component analysis based recognition algorithm. In online recognition, the proposed strategy cannot only classify motions correctly and identify the transition between different types of motions, but also identify the existence of an unknown motion type. This latter capability and the efficiency of the proposed strategy make it possible to create a real-time motion recognition system that can not only make classifications in real-time, but also learn new types of actions and recognize them in the future.

Training support vector machines involves a huge optimization problem and many specially designed algorithms have been proposed. In this paper, we proposed an algorithm called ClusterSVM that accelerates the training process by exploiting the distributional properties of the training data, that is, the natural clustering of the training data and the overall layout of these clusters relative to the decision boundary of support vector machines. The proposed algorithm first partitions the training data into several pair-wise disjoint clusters. Then, the representatives of these clusters are used to train an initial support vector machine, based on which we can approximately identify the support vectors and non-support vectors. After replacing the cluster containing only non-support vectors with its representative, the number of training data can be significantly reduced, thereby speeding up the training process. The proposed ClusterSVM has been tested against the popular training algorithm SMO on both the artificial data and the real data, and a significant speedup was observed. The complexity of ClusterSVM scales with the square of the number of support vectors and, after a further improvement, it is expected that it will scale with square of the number of non-boundary support vectors.

Many of the algorithms designed to cluster large data sets compute representations of the data which are based on a single vector, without a unique representation of the original data items. We present an extension of Principal Direction Divisive Partitioning which creates a least-squares approximation of the data based on a small number of vectors. We show that the extension can save significant amounts of memory and cluster the data as well as the original method. We also show that in some cases using more than one vector to approximate each data item results in superior quality clusterings.

1 Introduction The problem this paper focuses on is the classical problem of unsupervised clustering of a data-set. In particular, the bisecting divisive clustering approach is here considered. This approach consists in recursively splitting a cluster into two sub-clusters, starting from the main data-set. This is one of the more basic and common problems in fields like pattern analysis, data mining, document retrieval, image segmentation, decision making, etc. ([13], [15]).

1 Introduction and problem statement The problem this paper focuses on is the unsupervised clustering of a data-set. The dataset is given by the matrix M = [x1,x2,…,xN] ∊ ℜp×N, where each column of M, xi ∊ ℜp, is a single data-point. This is one of the more basic and common problems in fields like pattern analysis, data mining, document retrieval, image segmentation, decision making, etc. ([12, 13]). The specific problem we want to solve herein is the partition of M into two sub-matrices (or sub-clusters) ML ∊ ℜp×NL and MR ∊ ℜp×NR, NL + NR = N. This problem is known as bisecting divisive clustering.

The goal of toxicity prediction is to describe the relationship between chemical properties, on the one hand, and biological and toxicological processes, on the other. Knowledge about the causes of toxicity is incomplete. No single property can satisfy the requirement to model the toxic activity. In this study, we consider a different method, viz. building up models that are useful for aquatic toxicity prediction. Our study is in the tradition of SAR (structure-activity relationship) and QSAR (quantitative SAR) methods, but it tries to predict a category. Due to the variability of the toxicity phenomenon, classification methods may have advantages, because they refer to intervals of the observed toxic effect. Furthermore, the classification of compounds according to their toxicity has a direct application to the regulation of chemicals. In this paper, we report results obtained from the preparation and study of a data set of different classes of chemicals. Starting from recursive partitioning algorithms, we test their results against clustering and classifiers.

In the robot navigation problem, noisy sensor data must be filtered to obtain the best estimate of the robot position. We propose using a recursive total least squares algorithm to obtain estimates of the robot position. We avoid several weaknesses inherent in the use of the Kalman and extended Kalman filters, achieving much faster convergence without good initial (a priori) estimates of the position. The performance of the method is illustrated both by simulation and on an actual mobile robot with a camera.

We show how paths for articulated robots with many degrees of freedom can be generated in a few seconds or less using nonsystematic parallel search. We present experimental results obtained on a multicomputer for an accurate model of a 7-jointed manipulator arm operating in realistic 3D workspaces. We then present and discuss a fast method for smoothing the paths delivered by the parallel algorithm.

The paper introduces an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, Ax=b. Unlike previous methods, this backward error assertion model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and it can be easily instrumented in a Watchdog processor environment. The complexity of verifying assertions is O(n/sup 2/), compared to the O(n/sup 3/) complexity of algorithms solving Ax=b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.>

The convergence rate of the least mean squares (LMS) algorithm is poor whenever the adaptive filter input auto-correlation matrix is ill-conditioned. We propose a new LMS algorithm to alleviate this problem. It uses a data dependent signal transformation. The algorithm tracks the subspaces corresponding to clusters of eigenvalues of the auto-correlation matrix of the input to the adaptive filter, which have the same order of magnitude. The algorithm updates the projection of the tap weights of the adaptive filter onto each subspace using LMS algorithms with different step sizes. The technique also permits adaptation only in those subspaces, which contain strong signal components leading to a lower excess mean squared error (MSE) as compared to traditional algorithms.>

In this paper, we propose a novel Gabor transformation scheme that is based on the QR decomposition. This Gabor-QR scheme computes the exact Gabor coefficients by solving a system of linear equations Ax=b. The computation is more efficient than iterative schemes and less complicated than other matrix-based methods. In addition, the proposed Gabor-QR scheme allows the use of incomplete basis sets, which is uncommon in most matrix-based Gabor transformations. Experimental results from image encoding are presented to highlight the major contributions of the proposed method. Due to its computational efficiency, the Gabor-QR decomposition scheme has a strong potential as an efficient method for image sequence encoding.>

Multiple views of a scene can provide important information about the structure and dynamic behavior of three-dimensional objects. Many of the methods that recover this information require the determination of optical flow-the velocity, on the image, of visible points on object surfaces. An important class of techniques for estimating optical flow depend on the relationship between the gradients of image brightness. While gradient-based methods have been widely studied, little attention has been paid to accuracy and reliability of the approach. Gradient-based methods are sensitive to conditions commonly encountered in real imagery. Highly textured surfaces, large areas of constant brightness, motion boundaries, and depth discontinuities can all be troublesome for gradient-based methods. Fortunately, these problematic areas are usually localized can be identified in the image. In this paper we examine the sources of errors for gradient-based techniques that locally solve for optical flow. These methods assume that optical flow is constant in a small neighborhood. The consequence of violating in this assumption is examined. The causes of measurement errors and the determinants of the conditioning of the solution system are also considered. By understanding how errors arise, we are able to define the inherent limitations of the technique, obtain estimates of the accuracy of computed values, enhance the performance of the technique, and demonstrate the informative value of some types of error.