Skip to contents

Sparse-prefix computation

Source: vignettes/GLBFP_fast_sparse_computation.Rmd
GLBFP_fast_sparse_computation.Rmd

GLBFP uses a sparse-prefix traversal for finite-stencil grid-count density estimators. The estimator definition is unchanged. The implementation counts occupied grid cells once and prunes stencil branches that cannot reach an occupied cell.

library(GLBFP)

x <- cbind(rnorm(250), rnorm(250), rnorm(250))
b <- c(0.8, 0.8, 0.8)
m <- c(2, 2, 2)

fit <- glbfp_estimate(x, b = b, m = m, grid_size = 7)

c(
  grid_points = nrow(fit$grid),
  nominal_stencil = prod(2 * m),
  median_visited = median(fit$visited),
  median_prefix_nodes = median(fit$prefix_nodes)
)
#>         grid_points     nominal_stencil      median_visited median_prefix_nodes 
#>                 343                  64                   2                  44

The visited field records the number of nonzero occupied cells reached for each evaluation point. The prefix_nodes field records the number of explored prefix nodes. These diagnostics help assess whether sparsity is useful for a given data set and grid.

summary(fit)
#> Method: GLBFP 
#> Dimension: 3 
#> Grid points: 343 
#> Grid type: rectangular 
#> Grid dimensions: 7 x 7 x 7 
#> Bandwidths (b): 0.8, 0.8, 0.8 
#> Shifts (m): 2, 2, 2 
#> Density range: 0 to 0.0571137763588836 
#> Density quartiles: 0, 0.000794565016941354, 0.00477281652805236 
#> Density median: 0.000794565 
#> Density mean: 0.004230239 
#> Zero densities: 134 
#> Standard error median: 0.001499117 
#> Median visited cells: 2 
#> Median prefix nodes: 44

The sparse traversal also powers ASH_estimate() and LBFP_estimate().

ash_fit <- ash_estimate(x, b = b, m = m, grid_size = 7)
lbfp_fit <- lbfp_estimate(x, b = b, grid_size = 7)

rbind(
  ASH = c(median_visited = median(ash_fit$visited), max_visited = max(ash_fit$visited)),
  LBFP = c(median_visited = median(lbfp_fit$visited), max_visited = max(lbfp_fit$visited)),
  GLBFP = c(median_visited = median(fit$visited), max_visited = max(fit$visited))
)
#>       median_visited max_visited
#> ASH                1          14
#> LBFP               2           8
#> GLBFP              2          34

The sparse-prefix implementation is written in R for CRAN portability. It was adapted from the finite-stencil sparse traversal code used during the package development experiments.