# Two Block Diagonal Matrix Approximation. Finds the best two block diagonal matrix approximation of a similarity matrix according to some distance (linkage) function as described in Bauer (202Xa). Candidate splits are determined by the first sparse eigenvectors (sparse approximations of the first eigenvectors, i.e., vectors with many zero entries) of the similarity matrix. ```r bd.approx(S, linkage = "average", q = 1, h.power = 2, balance, max.iter) ``` ## 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"`, `"ncut"`, `"rcut"`, `"RV"` (for RV-coefficient), or `"single"`. - `q`: Number of sparse eigenvectors to be used. This should be either a numeric value between zero and one to indicate percentages, or `"Kaiser"` for as many sparse eigenvectors as there are eigenvalues larger or equal to one. 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. E.g., `q = 1` (100%) uses all sparse eigenvectors and `q = 0.5` (50%) will use half of all sparse eigenvectors. For `q = 1`, identification is best (see Bauer (202Xa) for details). - `h.power`: `h`-th Hadamard power of `S`. This should be a positive integer and increases robustness of the method, as described in Bauer (202Xa). - `balance`: Minimum proportion of the smaller block when splitting into two. Must be a numeric value in $(0, 0.5]$. For example, `balance = 0.5` enforces an exact 50:50 split, while `balance = 0.2` allows splits as unbalanced as 20:80, with more balanced splits such as 30:70 or 40:60 also permitted. If an exact split is not possible (e.g., `balance = 0.5` when $p = 9$), the closest integer partition is used (e.g., 4 and 5 per block). - `max.iter`: How many iterations should be performed for computing the sparse eigenvectors. Default is `500`. ## Returns A list with four components: - **B**: The best two block diagonal matrix approximation. - **BD**: The best two block diagonal matrix approximation permuted to a block diagonal shape: $BD = P B t(P)$. - **P**: The permutation matrix $P$: $BD = P B t(P)$. - **clustering**: The clustering vector as an integer vector of length $p$, which gives for each component the number `1` or `2` of the cluster/split to which it belongs. - **split**: A `list` containing the two splits. - **distance**: The approximation error (distance) according to the selected linkage function. ## Details The sparse eigenvectors are computed using the method of Shen and Huang (2008). The method is implemented by Baglama, Reichel, and Lewis in `ssvd` (`irlba`). Here, we use a `Rcpp`/`RcppArmadillo` implementation based on `ssvd` with slight modifications to suit our method and for faster performance. ## Examples ```r #We give a trivial example for a block diagonal matrix perturbed by #noise, for adapting clustering objectives of spectral clustering, #and for balanced clustering. ### TOY EXAMPLE A <- matrix(c(2,1,1,3), 2, 2) # 2x2 block B <- matrix(c(5,4,4,6), 2, 2) # 2x2 block # Create a 5x5 zero matrix and insert blocks at right positions. M <- matrix(0, 4, 4) M[1:2, 1:2] <- A M[3:4, 3:4] <- B M.tilde <- M + matrix(rnorm(4^2, 0, 0.2), 4, 4) #Construct a similaritiy matrix with same block structure S <- cov2cor(t(M.tilde) %*% M.tilde) bd <- bd.approx(S) #Block diagonal approximation: bd$B #We can also permute the block diagonal shape: S2 <- S[c(1, 3, 2, 4), c(1, 3, 2, 4)] bd2 <- bd.approx(S2) #bd2$B gives us again the block diagonal approximation bd2$B #And bd2$BD gives us the block diagonal approximation permuted to #block diagonal shape bd2$BD ### ADAPTING CLUSTERING OBJECTIVES #We will use the USArrests example (see ?hcsvd). data("USArrests") USArrests["Maryland", "UrbanPop"] <- 76.6 D <- as.matrix(dist(USArrests)) S <- 1 - D / max(D) #We compute k = 2 clusters adapting the objective of spectral clustering #with the ratio cut. bd.approx(S, linkage = "rcut") ### BALANCED CLUSTERING #We can also enforce balanced clustering, such as two clusters of equal #size (50:50). We will do this for the USArrests example from above. bd.approx(S, linkage = "rcut", balance = 0.5) ``` ## References Bauer, J.O. (202Xa). Divisive hierarchical clustering using blockdiagonal matrix approximations. Working paper. Shen, H. and Huang, J.Z. (2008). Sparse principal component analysisvia regularized low rank matrix approximation, J. Multivar. Anal. 99,1015–1034.

bd.approx function