Treelets—An adaptive multi-scale basis for sparse unordered data

2007/07/31 by Ann B. Lee, Boaz Nadler, Larry Wasserman · 7 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #Gene expression and cancer classification #stat.ME

paper · pdf · doi:10.1214/07-aoas137

published as Annals of Applied Statistics 2008, Vol. 2, No. 2, 435-471 · This paper commented in: [arXiv:0807.4011], [arXiv:0807.4016], [arXiv:0807.4018], [arXiv:0807.4019], [arXiv:0807.4023], [arXiv:0807.4024]. Rejoinder in [arXiv:0807.4028]. Published in at http://dx.doi.org/10.1214/07-AOAS137 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

openalex publication_date 2008/06/01 · arxiv created 2008/07/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

In many modern applications, including analysis of gene expression and text documents, the data are noisy, high-dimensional, and unordered—with no particular meaning to the given order of the variables. Yet, successful learning is often possible due to sparsity: the fact that the data are typically redundant with underlying structures that can be represented by only a few features. In this paper we present treelets—a novel construction of multi-scale bases that extends wavelets to nonsmooth signals. The method is fully adaptive, as it returns a hierarchical tree and an orthonormal basis which both reflect the internal structure of the data. Treelets are especially well-suited as a dimensionality reduction and feature selection tool prior to regression and classification, in situations where sample sizes are small and the data are sparse with unknown groupings of correlated or collinear variables. The method is also simple to implement and analyze theoretically. Here we describe a variety of situations where treelets perform better than principal component analysis, as well as some common variable selection and cluster averaging schemes. We illustrate treelets on a blocked covariance model and on several data sets (hyperspectral image data, DNA microarray data, and internet advertisements) with highly complex dependencies between variables.

Citations

• Discussion of: Treelets--An adaptive multi-Scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Rejoinder of: Treelets--An adaptive multi-scale basis for spare unordered data
• On the distribution of the largest eigenvalue in principal components analysis
• Sparse Principal Component Analysis
• Model-Based Clustering, Discriminant Analysis, and Density Estimation
• Regularized estimation of large covariance matrices
• Survey of Clustering Algorithms
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm

Cited by

• Discussion of: Treelets--An adaptive multi-Scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Discussion of: Treelets--An adaptive multi-scale basis for sparse unordered data
• Rejoinder of: Treelets--An adaptive multi-scale basis for spare unordered data