use std::cell::RefCell;
use crate::error::{finite, invalid};
use crate::{FitError, Penalty, ProximalPenalty};
#[derive(Clone, Debug)]
pub struct Slope {
weights: Vec<f64>,
scratch: RefCell<Workspace>,
}
#[derive(Clone, Debug)]
struct Workspace {
order: Vec<usize>,
blocks: Vec<Block>,
thresholds: Vec<f64>,
}
#[derive(Clone, Copy, Debug)]
struct Block {
start: usize,
end: usize,
mean: f64,
}
impl Slope {
pub fn new(weights: Vec<f64>) -> Self {
let length = weights.len();
Self {
weights,
scratch: RefCell::new(Workspace {
order: (0..length).collect(),
blocks: Vec::with_capacity(length),
thresholds: Vec::new(),
}),
}
}
pub fn weights(&self) -> &[f64] {
&self.weights
}
pub(crate) fn sorted_bound_indices<T>(
&self,
length: usize,
bound: impl Fn(usize) -> f64,
inspect: impl FnOnce(&[usize]) -> T,
) -> T {
let mut scratch = self.scratch.borrow_mut();
scratch.order.clear();
scratch.order.extend(0..length);
scratch
.order
.sort_unstable_by(|&a, &b| bound(b).total_cmp(&bound(a)).then(a.cmp(&b)));
inspect(&scratch.order)
}
pub(crate) fn with_screening_order<T>(
&self,
zeroed: &mut [bool],
bound: impl Fn(usize) -> f64,
inspect: impl FnOnce(&[usize], &mut [f64], &mut [bool]) -> T,
) -> T {
let mut scratch = self.scratch.borrow_mut();
scratch.order.clear();
scratch
.order
.extend((0..zeroed.len()).filter(|&j| !zeroed[j]));
scratch
.order
.sort_unstable_by(|&a, &b| bound(b).total_cmp(&bound(a)).then(a.cmp(&b)));
let length = scratch.order.len();
scratch.thresholds.resize(length, 0.0);
let Workspace {
order, thresholds, ..
} = &mut *scratch;
inspect(order, thresholds, zeroed)
}
fn validate(&self, input: &[f64]) -> Result<(), FitError> {
if self
.weights
.iter()
.any(|weight| !weight.is_finite() || *weight < 0.0)
{
return Err(invalid("SLOPE weights must be finite and nonnegative"));
}
if self.weights.windows(2).any(|pair| pair[0] < pair[1]) {
return Err(invalid("SLOPE weights must be nonincreasing"));
}
if input.len() != self.weights.len() {
return Err(invalid("SLOPE requires one weight per coefficient"));
}
if input.iter().any(|value| !value.is_finite()) {
return Err(invalid("SLOPE input must be finite"));
}
Ok(())
}
}
impl Workspace {
fn sort(&mut self, input: &[f64]) {
self.order.clear();
self.order.extend(0..input.len());
self.order
.sort_unstable_by(|&a, &b| input[b].abs().total_cmp(&input[a].abs()).then(a.cmp(&b)));
}
}
impl Penalty for Slope {
type Error = FitError;
fn value(&self, coefficients: &[f64]) -> Result<f64, FitError> {
self.validate(coefficients)?;
let mut scratch = self.scratch.borrow_mut();
scratch.sort(coefficients);
let value = scratch
.order
.iter()
.zip(&self.weights)
.map(|(&index, &weight)| weight * coefficients[index].abs())
.sum();
Ok(finite(value, "computing the SLOPE penalty", 0)?)
}
fn validate_input(&self, coefficients: &[f64]) -> Result<(), FitError> {
self.validate(coefficients)
}
}
impl ProximalPenalty for Slope {
fn gap_safe(&self) -> Option<&dyn crate::screening::GapSafePenalty> {
Some(self)
}
fn prox(&self, input: &[f64], step: f64, output: &mut [f64]) -> Result<(), FitError> {
self.prox_impl(input, None, step, output)
}
}
impl Slope {
pub(crate) fn prox_screened(
&self,
input: &[f64],
zeroed: &[bool],
step: f64,
output: &mut [f64],
) -> Result<(), FitError> {
if input.len() != zeroed.len() {
return Err(invalid("zero mask length must match the coefficients"));
}
self.prox_impl(input, Some(zeroed), step, output)
}
fn prox_impl(
&self,
input: &[f64],
zeroed: Option<&[bool]>,
step: f64,
output: &mut [f64],
) -> Result<(), FitError> {
self.validate(input)?;
if output.len() != input.len() {
return Err(invalid("proximal input and output lengths must match"));
}
if !step.is_finite() || step <= 0.0 {
return Err(invalid(
"proximal step must be finite and strictly positive",
));
}
let mut scratch = self.scratch.borrow_mut();
scratch.sort(input);
if let Some(mask) = zeroed {
scratch.order.retain(|&index| !mask[index]);
}
output.fill(0.0);
let Workspace { order, blocks, .. } = &mut *scratch;
blocks.clear();
for (rank, (&index, &weight)) in order.iter().zip(&self.weights).enumerate() {
let threshold = finite(step * weight, "computing a SLOPE proximal threshold", 0)?;
blocks.push(Block {
start: rank,
end: rank + 1,
mean: input[index].abs() - threshold,
});
while blocks.len() > 1 {
let last = blocks.len() - 1;
let (left, right) = (blocks[last - 1], blocks[last]);
if left.mean > right.mean {
break;
}
let mean = if left.mean == right.mean {
left.mean
} else {
let fraction =
(right.end - right.start) as f64 / (right.end - left.start) as f64;
left.mean * (1.0 - fraction) + right.mean * fraction
};
blocks[last - 1] = Block {
start: left.start,
end: right.end,
mean: finite(mean, "pooling SLOPE proximal blocks", 0)?,
};
blocks.pop();
}
}
for block in blocks.iter() {
for &index in &order[block.start..block.end] {
output[index] = block.mean.max(0.0).copysign(input[index]);
}
}
Ok(())
}
}