hcsvd: Hierarchical Clustering Using Singular Vectors (HC-SVD).

Description

Performs HC-SVD to reveal the hierarchical structure as described in Bauer (202X). This divisive approach iteratively splits each cluster into two subclusters. By default, candidate splits are determined by sparse approximations of the first eigenvectors of the similarity matrix. For small clusters, an exhaustive search over all unique two-way partitions can alternatively be used. The selected split is the one that yields the best block-diagonal approximation of the similarity matrix according to a specified linkage function. The procedure continues until each object is assigned to its own cluster.

Usage

hcsvd(
  S,
  linkage = "average",
  q = 1,
  h.power = 2,
  max.iter,
  verbose = TRUE,
  search = "hcsvd",
  exhaustive.max.p = 20
)

Value

A list containing:

hclust: The clustering structure identified by HC-SVD as an object of type hclust. For linkage = "RV", dendrogram heights are monotonically adjusted if required because the RV-coefficient need not yield an ultrametric distance.
dist.matrix: The distance matrix of the HC-SVD structure as an object of class dist. This matrix need not be ultrametric for linkage = "RV".
u.sim: The corresponding similarity matrix of \(S\), calculated as 1-dist.matrix.
q.p: A vector of length \(p-1\) containing the ratio \(q_i/p_i\) of the number of sparse eigenvectors used relative to the total number of eigenvectors for the split of each cluster. Since HC-SVD uses at most \(p_i-1\) sparse eigenvectors, this ratio is always smaller than one. The ratio is set to NA when exhaustive search is used or when the cluster contains only two objects, since no sparse eigenvectors are computed in these cases.
search: A vector indicating whether "hcsvd", "exhaustive", or the unique two-object split was used at each recursive step.

Arguments

S: A scaled \(p\)x\(p\) similarity matrix. For example, this may be a correlation matrix.
linkage: The linkage function to be used. This should be one of "average", "single", or "RV" (for RV-coefficient). Note that the RV-coefficient might not yield an ultrametric distance.
q: Number of sparse eigenvectors to be used whenever the HC-SVD search is applied. This should be either a numeric value between zero and one to indicate percentages, or "Kaiser". For a numerical value between zero and one, the number of sparse eigenvectors is determined as the corresponding share of the total number of eigenvectors, capped at \(p-1\). E.g., q = 1 uses all \(p-1\) available sparse eigenvectors. The Kaiser rule uses the number of eigenvalues of the Hadamard-transformed similarity matrix that are at least one, plus two additional eigenvectors, capped at \(p-1\).
h.power: h-th Hadamard power of S used whenever sparse-eigenvector candidate generation is applied. This should be a positive integer. Larger powers shrink similarities with magnitude smaller than one towards zero and can increase the contrast between within- and between-block similarities, although their effect depends on the similarity structure and clustering objective.
max.iter: How many iterations should be performed for computing the sparse eigenvectors when the HC-SVD search is used. Default is 500.
verbose: Print out progress as \(p-1\) iterations for divisive hierarchical clustering are performed. Default is TRUE.
search: Search strategy. "hcsvd" uses sparse-eigenvector candidate generation, "exhaustive" evaluates all unique two-way partitions for the selected linkage function only, and "auto" uses exhaustive search whenever the current cluster contains at most exhaustive.max.p objects and HC-SVD otherwise.
exhaustive.max.p: Largest cluster size for which exhaustive search is used when search = "auto". Default is 20. The exhaustive C++ implementation is restricted to at most 30 objects.

Details

The sparse loadings are computed using the method proposed by Shen & Huang (2008). The corresponding implementation is written in Rcpp/RcppArmadillo for computational efficiency and is based on the R implementation by Baglama, Reichel, and Lewis in ssvd {irlba}. However, the implementation has been adapted to better align with the scope of the bdsvd package which is the base for the blox package.

Supplementary details are in hc.beta and in Bauer (2026).

References

Bauer, J.O. (2026). Revelle’s beta: The wait is over—computation becomes possible. Psychometrika.

Bauer, J.O. (202X). Divisive hierarchical clustering using block diagonal matrix approximations. Working paper.

Shen, H. and Huang, J.Z. (2008). Sparse principal component analysis via regularized low rank matrix approximation, J. Multivar. Anal. 99, 1015–1034.

Examples

Run this code

#We give one example for variable clustering directly on a correlation matrix,
#and we replicate the USArrest example in Bauer (202X) for observation clustering.
#More elaborate code alongside a different example for variable clustering can be
#found in the corresponding supplementary material of that manuscripts.

# \donttest{
### VARIABLE CLUSTERING

#Load the correlation matrix Bechtoldt from the psych
#package (see ?Bechtoldt for more information).
if (requireNamespace("psych", quietly = TRUE)) {
  data("Bechtoldt", package = "psych")
}

#Compute HC-SVD (with average linkage).
hcsvd.obj <- hcsvd(Bechtoldt)

#The object of type hclust with corresponding dendrogram can be obtained
#directly from hcsvd(...):
hc.div <- hcsvd.obj$hclust
plot(hc.div, ylab = "")

#The dendrogram can also be obtained from the ultrametric distance matrix:
plot(hclust(hcsvd.obj$dist.matrix), main = "HC-SVD", sub = "", xlab = "")


### OBSERVATION CLUSTERING

#Correct for the known transcription error
data("USArrests")
USArrests["Maryland", "UrbanPop"] <- 76.6

#The distance matrix is scaled (divided by max(D)) to later allow a
#transformation to a matrix S that fulfills the properties of a similarity
#matrix.
D <- as.matrix(dist(USArrests))
D <- D / max(D)
S <- 1 - D

#Compute HC-SVD (with average linkage).
hcsvd.obj <- hcsvd(S)

#The object of type hclust with corresponding dendrogram can be obtained
#directly from hcsvd(...):
hc.div <- hcsvd.obj$hclust
plot(hc.div, ylab = "")

#The dendrogram can also be obtained from the ultrametric distance matrix:
plot(hclust(hcsvd.obj$dist.matrix), main = "HC-SVD", sub = "", xlab = "")
# }

Run the code above in your browser using DataLab