Solving least squares (LS) problems is a major topic in many applications. With recent data explosion, traditional approach is no longer suitable while working with large datasets, instead, randomized algorithms become popular in addressing this issue. In this article we propose a new randomized algorithm - sparse subsampled randomized Hadamard transform (SpSRHT) for solving overdetermined least squares problems. Its unique block structure connects two most commonly used randomized algorithms subsampled randomized Hadamard transform (SRHT) and sparse subspace embedding (SpEmb) and creates a general framework which contains them as special cases. We have shown theoretically that SpSRHT with different parameters reaches the relative-error bound with sketch size ranging from the sketch size required by SpEmb to SRHT. The new algorithm closes the gap between SRHT and SpEmb which provides the possibility of balancing accuracy and efficiency demonstrated in them. This advantage of SpSRHT is also well illustrated in our numerical experiments.

We consider the topic of multivariate regression on manifold-valued output, that is, for a multivariate observation, its output response lies on a manifold. Moreover, we propose a new regression model to deal with the presence of grossly corrupted manifold-valued responses, a bottleneck issue commonly encountered in practical scenarios. Our model first takes a correction step on the grossly corrupted responses via geodesic curves on the manifold, then performs multivariate linear regression on the corrected data. This results in a nonconvex and nonsmooth optimization problem on Riemannian manifolds. To this end, we propose a dedicated approach named PALMR, by utilizing and extending the proximal alternating linearized minimization techniques for optimization problems on euclidean spaces. Theoretically, we investigate its convergence property, where it is shown to converge to a critical point under mild conditions. Empirically, we test our model on both synthetic and real diffusion tensor imaging data, and show that our model outperforms other multivariate regression models when manifold-valued responses contain gross errors, and is effective in identifying gross errors.

In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality by means of symmetrization, we propose a novel random walk approach on directed graphs using absorbing Markov chains, which can be regarded as maximizing the accumulated expected number of visits from the unlabeled transient states. Our algorithm is simple, easy to implement, and works with large-scale graphs on binary, multiclass, and multi-label prediction problems. Moreover, it is capable of preserving the graph structure even when the input graph is sparse and changes over time, as well as retaining weak signals presented in the directed edges. We present its intimate connections to a number of existing methods, including graph kernels, graph Laplacian based methods, and spanning forest of graphs. Its computational complexity and the generalization error are also studied. Empirically, our algorithm is evaluated on a wide range of applications, where it has shown to perform competitively comparing to a suite of state-of-the-art methods. In particular, our algorithm is shown to work exceptionally well with large sparse directed graphs with e.g., millions of nodes and tens of millions of edges, where it significantly outperforms other state-of-the-art methods. In the dynamic graph setting involving insertion or deletion of nodes and edge-weight changes over time, it also allows efficient online updates that produce the same results as of the batch update counterparts.

We focus on the challenging problem of filamentary structure segmentation in both 2D and 3D images, including retinal vessels and neurons, among others. Despite the increasing amount of efforts in learning based methods to tackle this problem, there still lack proper data-driven feature construction mechanisms to sufficiently encode contextual labelling information, which might hinder the segmentation performance. This observation prompts us to propose a data-driven approach to learn structured and contextual features in this paper. The structured features aim to integrate local spatial label patterns into the feature space, thus endowing the follow-up tree classifiers capability to grouping training examples with similar structure into the same leaf node when splitting the feature space, and further yielding contextual features to capture more of the global contextual information. Empirical evaluations demonstrate that our approach outperforms state-of-the-arts on well-regarded testbeds over a variety of applications. Our code is also made publicly available in support of the open-source research activities.

This paper aims to tackle the practically very challenging problem of efficient and accurate hand pose estimation from single depth images. A dedicated two-step regression forest pipeline is proposed: given an input hand depth image, step one involves mainly estimation of 3D location and in-plane rotation of the hand using a pixel-wise regression forest. This is utilized in step two which delivers final hand estimation by a similar regression forest model based on the entire hand image patch. Moreover, our estimation is guided by internally executing a 3D hand kinematic chain model. For an unseen test image, the kinematic model parameters are estimated by a proposed dynamically weighted scheme. As a combined effect of these proposed building blocks, our approach is able to deliver more precise estimation of hand poses. In practice, our approach works at 15.6 frame-per-second (FPS) on an average laptop when implemented in CPU, which is further sped-up to 67.2 FPS when running on GPU. In addition, we introduce and make publicly available a data-glove annotated depth image dataset covering various hand shapes and gestures, which enables us conducting quantitative analyses on real-world hand images. The effectiveness of our approach is verified empirically on both synthetic and the annotated real-world datasets for hand pose estimation, as well as related applications including part-based labeling and gesture classification. In addition to empirical studies, the consistency property of our approach is also theoretically analyzed.

The aim of this study is about tracing filamentary structures in both neuronal and retinal images. It is often crucial to identify single neurons in neuronal networks, or separate vessel tree structures in retinal blood vessel networks, in applications such as drug screening for neurological disorders or computer-aided diagnosis of diabetic retinopathy. Both tasks are challenging as the same bottleneck issue of filament crossovers is commonly encountered, which essentially hinders the ability of existing systems to conduct large-scale drug screening or practical clinical usage. To address the filament crossovers' problem, a two-step graph-theoretical approach is proposed in this paper. The first step focuses on segmenting filamentary pixels out of the background. This produces a filament segmentation map used as input for the second step, where they are further separated into disjointed filaments. Key to our approach is the idea that the problem can be reformulated as label propagation over directed graphs, such that the graph is to be partitioned into disjoint sub-graphs, or equivalently, each of the neurons (vessel trees) is separated from the rest of the neuronal (vessel) network. This enables us to make the interesting connection between the tracing problem and the digraph matrix-forest theorem in algebraic graph theory for the first time. Empirical experiments on neuronal and retinal image datasets demonstrate the superior performance of our approach over existing methods.

Linear discriminant analysis (LDA) as a well-known supervised dimensionality reduction method has been widely applied in many fields. However, the lack of sparsity in the LDA solution makes interpretation of the results challenging. In this paper, we propose a new model for sparse uncorrelated LDA (ULDA). Our model is based on the characterization of all solutions of the generalized ULDA. We incorporate sparsity into the ULDA transformation by seeking the solution with minimum ℓ1-norm from all minimum dimension solutions of the generalized ULDA. The problem is then formulated as an ℓ1-minimization problem with orthogonality constraint. To solve this problem, we devise two algorithms: 1) by applying the linearized alternating direction method of multipliers and 2) by applying the accelerated linearized Bregman method. Simulation studies and high-dimensional real data examples demonstrate that our algorithms not only compute extremely sparse solutions but also perform well in classification.

In this paper, we develop a novel approach for sparse uncorrelated linear discriminant analysis (ULDA). Our proposal is based on characterization of all solutions of the generalized ULDA. We incorporate sparsity into the ULDA transformation by seeking the solution with minimum \ell_1-norm from all minimum dimension solutions of the generalized ULDA. The problem is then formulated as a \ell_1-minimization problem and is solved by accelerated linearized Bregman method. Experiments on high-dimensional gene expression data demonstrate that our approach not only computes extremely sparse solutions but also performs well in classification. Experimental results also show that our approach can help for data visualization in low-dimensional space.

In this paper, we study canonical correlation analysis (CCA), which is a powerful tool in multivariate data analysis for finding the correlation between two sets of multidimensional variables. The main contributions of the paper are: 1) to reveal the equivalent relationship between a recursive formula and a trace formula for the multiple CCA problem, 2) to obtain the explicit characterization for all solutions of the multiple CCA problem even when the corresponding covariance matrices are singular, 3) to develop a new sparse CCA algorithm, and 4) to establish the equivalent relationship between the uncorrelated linear discriminant analysis and the CCA problem. We test several simulated and real-world datasets in gene classification and cross-language document retrieval to demonstrate the effectiveness of the proposed algorithm. The performance of the proposed method is competitive with the state-of-the-art sparse CCA algorithms.