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

• High-dimensional data may be noisy and unordered, while sparsity can arise when redundant variables reflect a few underlying features.The paper distinguishes this data-structure sparsity from sparsity in learning parameters or covariance quantities.Source: §1 · p. 2
• PCA uses a global representation that can obscure localized groups, while standard wavelets assume smoothness and are not suited to unordered data.Reordering variables before applying fixed wavelets has also been proposed.Source: §1 · pp. 3–4
• Treelets adaptively build a multiscale orthogonal basis and hierarchical tree for variables in any order.The method targets data representation and dimensionality reduction before learning in large-p, small-n settings.Source: §1 · p. 4
• The basis functions encode data geometry, while their expansion coefficients indicate coordinate importance.The simultaneous basis and tree construction is the approach's stated novelty.Source: §1 · pp. 4–5
• Treelets are designed to reflect localized structure and remain stable to noise; correlated groups can yield sparse bases with dominant functions acting like group indicators.For more complex structure, the loadings can instead be continuous-valued; discriminant functions may compute differences between variable groups.Source: §1 · p. 5

2. The treelet transform.

• Treelets construct both variable groupings and functions on a hierarchical tree, yielding scaling functions on nested subspaces and orthogonal detail functions on residual spaces.The resulting decomposition is technically not a wavelet transform.Source: §2 · p. 6
• The similarity between variables is measured using correlation, with other similarity measures also possible.Options include absolute correlation or a weighted combination of absolute correlation and covariance.Source: §2 · p. 6

2.1. The algorithm: Jacobi rotations on pairs of similar variables.

• At each level, the algorithm groups the most similar variables and replaces them with a coarse sum and a residual difference computed by local two-dimensional PCA.Difference variables are retained, while only sum variables are processed at higher levels.Source: §2.1 · p. 6

• The pair search is restricted to sum variables, leaving difference variables out of subsequent processing.Source: §1 · p. 7

• A Jacobi rotation chooses an angle that decorrelates the selected pair, then updates the covariance, basis, coordinates, and similarity matrix.The rotation angle is constrained to |θℓ| ≤ π/4.Source: §2 · p. 7

3. Multi-resolution analysis.

• A treelet basis is built by repeatedly rotating the two most similar sum variables into sum and difference coordinates, producing scaling and detail projections.The sums give a coarse-grained representation; the differences capture residuals at different scales.Source: §3 · pp. 7–8
• With stored similarity matrices and tracked local updates, treelet computation costs m + O(Lp), comparable to hierarchical clustering.A naive exhaustive pair search costs m + O(Lp^2), where m is the sample-covariance computation cost.Source: §3 · p. 8
• The default tree has maximum height L = p − 1; shorter levels retain coarse sums for clusters and differences for finer detail.Alternative stopping rules include a similarity threshold or cluster-homogeneity tests.Source: §2.2 · pp. 8–9

2.2. Selecting the height L of the tree and a “best K-basis.”

• For a chosen dimension K, the best K-basis is the treelet basis whose K highest-energy coordinates maximize explained variance.Cross-validation estimates the score on independent test sets to avoid overfitting.Source: §2.2 · p. 9
• The energy score can be replaced by criteria suited to the task, including discriminant scores, classification error, entropy, or sparsity measures.For classification, the paper proposes a discriminant score measuring how well a coordinate separates classes.Source: §2.2 · p. 10

3.1. Large sample properties of the treelet transform.

• A bootstrap procedure can quantify treelet stability, with the stated confidence-set result applying when the distribution has finite fourth moments and p is fixed.The paper also states large-sample assumptions on finite variance and dimension growth, including bounded variables, multivariate normality, or a moment condition.Source: §3 · p. 10, §3.1 · pp. 10–11
• Correlation-based treelet transforms need not converge to the transform of the population covariance: sample fluctuations can select different rotations, which the authors regard as reasonable alternatives.Near-tied correlations between pairs with different covariance submatrices illustrate this instability.Source: §3.1 · pp. 10–11

3.2.1. An exact analysis in the limit n →∞.

• For statistically indistinguishable variables, treelets produce scaling functions constant on groups, including an indicator-like function for a full block; this relies on adaptive bases and tree structure.The paper contrasts this with fixed wavelets on data-driven trees [Murtagh (2007)] and adaptive bases on fixed trees [Coifman and Saito (1996)].Source: §3.2.1 · p. 12
• Uncorrelated additive noise may alter grouping order without changing the lemma’s asymptotic results; after correct coarse variables form, the transform has a denoising effect.The analysis treats within-block correlations at singleton merges as a worst case.Source: §3.2.1 · pp. 12, 14
• With weak between-block correlations and sufficiently small noise, the K maximum-variance scaling functions are constant on their respective blocks.In a full decomposition, block-constant scaling and detail functions reflect between-block structure, while the earlier detail coefficients reflect only noise; energy distribution can identify K without a parameter choice.Source: §3.2.1 · pp. 13–14

3.2.2. Convergence rates.

• Treelets are consistent for finding variable groupings when n ≫ O(log p), compared with PCA consistency only when p/n → 0, or n ≫ O(p) [Johnstone and Lu (2008)].The comparison is for the stated block covariance setting; the cited sparse-covariance result assumes an a priori variable ordering, whereas treelets find an ordering and coordinate system.Source: §3.2.2 · pp. 15–16

4.1. Treelets and a linear mixture model in the unsupervised setting.

• With uncorrelated factors, nonoverlapping loading vectors, and strong signals, PCA and treelets both recover the hidden vectors as sample size tends to infinity.The treelet height is chosen by cross-validation and a normalized energy criterion.Source: §4.1 · p. 17
• For consistency in the joint large-p, large-n limit, PCA requires p(n)/n → 0, whereas treelets require log p(n)/n → 0.The stated treelet condition requires asymptotically fewer observations than PCA's condition.Source: §4.1 · pp. 17–18
• With correlated factors and nonoverlapping loadings, PCA struggles to recover localized structure, while treelets identify the components and hidden loading vectors without prior block-size information or tuning.The three maximum-energy treelets correspond exactly to the hidden loading vectors in the example.Source: §4.1 · pp. 18–19, Figure 2 · p. 19
• In a small-sample, noisy example with overlapping loading vectors, treelets remain stable and largely identify the data's internal structure, with leading treelets approximating the loading-vector span.The example has n = 100 observations, p = 500 variables, and noise variance comparable to factor variances.Source: §4.1 · pp. 20–21
• The energy distribution of a full treelet decomposition offers a parameter-free way to estimate the number of blocks, and treelets can reveal block structure amid many background-noise variables.In the overlapping-loading example, cross-validation indicated a tree height of L = 300.Source: §4.1 · p. 20

4.2. The treelet transform as a feature selection scheme prior to regression.

• A useful dimensionality reduction should preserve the net analyte signal while representing data with far fewer features; treelets are proposed for unstructured data.Wavelets are described as a reasonable choice when signals are known a priori to be smooth.Source: §4.2 · p. 23
• MSEP was 0.035 for PLS on 50 highest-variance treelet features, versus 0.17 for PLS on all variables, 0.09 for supervised variable-selection PLS, and 0.030 on true-vector projections.The treelet-feature result is described as near optimal.Source: Figure 4 · p. 24, §4.2 · pp. 24–25

5.1. Hyperspectral analysis and classification of biomedical tissue.

• In the tissue example, treelet basis vectors were localized on nested clusters, whereas PCA eigenvectors involved all original spectral variables.The treelet basis and tree were learned through successive Jacobi rotations.Source: §5.1 · p. 25, Figure 6 · p. 27
• Three treelet features matched the classifier’s performance on all 28 spectral components, and using more features lowered the misclassification rate.The authors attribute the improvement to denoising through a changed coordinate system and discarding irrelevant coordinates.Source: §5.1 · p. 26

5.2. A classification example with an internet advertisement data set.

• Treelets exposed correlated advertisement-variable groups, compressed 1,555 binary variables to 760 without information loss, and further improved prediction on the reduced data.The remaining variables included more than 200 pairs with correlation above 0.95; Table 1 reports classification test errors.Source: §5.2 · pp. 28–29, Table 1 · p. 28

5.3. Classification and analysis of DNA microarray data.

• Treelets also provide a hierarchical reordering and an orthogonal representation for exploring, interpreting, and compressing microarray data.The method returns orthogonal functions carrying continuous-valued information about hierarchical groupings of genes or samples.Source: §5.3 · pp. 30, 32
• For two-way decomposition of genes and samples, ten-fold cross-validation yielded 0/38 misclassified cases at K = 4 treelet features, followed by 1/34 test errors; LDA had 2/38 at K = 3 and 3/34 test errors.Source: Figure 9 · p. 31
• For leukemia data, treelet loadings reflected complex structure and coarse-grained variables represented groups of highly correlated genes or samples.The highest-energy treelets on ordered samples included a continuous-valued indicator of the true classes.Source: Figure 10 · p. 31, §5.3 · p. 32

APPENDIX

• x denotes a p-dimensional random vector with distribution F and covariance matrix Σ = Σ_F.Source: §A.1 · p. 33
• The sample x_1,...,x_n has sample covariance matrix ˆΣ and sample correlations ˆρ_ij.Source: §A.1 · p. 33
• S_p denotes the set of all p × p covariance matrices.Source: §A.1 · p. 33

A.1. Proof of Theorem 1.

• Any one of assumptions (A1a), (A1b), or (A1c) suffices for the stated exponential inequalities.Source: §A.1 · p. 33
• Under (A1), the proof obtains a covariance-estimation bound using exponential inequalities and a union bound, then selects a logarithmic-rate sequence under (A2).The proof sets ǫ_n = K√(log n/n) for sufficiently large K.Source: §A.1 · p. 33
• For correlation concentration, the stated conditions are multivariate normality or bounded coordinates with variances bounded away from zero.The proof applies a bounded, smooth correlation function to the covariance bound.Source: §A.1 · p. 33
• The operator selects a pair with maximum correlation and applies a Jacobi rotation; ties make the selection and one-step map multivalued.Source: §A.1 · p. 34

Proof of Theorem 1.

• The sample covariance matrix is within δ_n of Σ in the infinity norm except on an event whose probability tends to zero at rate O(n^-(K-2c)).Source: Proof of Theorem 1 · p. 34
• When the sample covariance is within the stated neighborhood, the sample one-step operator output belongs to T_n(Σ).Source: Proof of Theorem 1 · p. 34
• The proof applies the same neighborhood argument at each step of the treelet procedure.Source: Proof of Theorem 1 · p. 34

A.2. Proof of Lemma 1.

• At each level, the lemma considers combining sum variables over disjoint index subsets and applies PCA to their covariance submatrix, which has eigenvalues m+n and 0.Source: §A.2 · pp. 34–35

A.3. Proof of Theorem 2.

• The within-block correlation bound is weakest when two singletons are merged, while the proof also bounds between-block correlations.Source: §A.3 · pp. 35–36
• Under inequality (13), variables from different blocks are not combined through levels ℓ=1,...,p−K, and the treelet coefficients retain their stated general form.Source: §A.3 · p. 36