use crate::application::linalg::qr::qr_decompose;
use leto::{Array1, Array2, ArrayView1, ArrayView2, LetoError, Result as LetoResult};
#[derive(Debug, Clone, Copy)]
pub struct NnlsConfig {
pub max_iterations: usize,
pub tolerance: f64,
}
impl Default for NnlsConfig {
fn default() -> Self {
Self {
max_iterations: 500,
tolerance: 1e-8,
}
}
}
#[derive(Debug, Clone)]
pub struct NnlsResult {
pub solution: Array1<f64>,
pub residual_norm: f64,
pub iterations: usize,
pub converged: bool,
}
pub fn nnls(
a: &ArrayView2<'_, f64>,
b: &ArrayView1<'_, f64>,
config: NnlsConfig,
) -> LetoResult<NnlsResult> {
let [m, n] = a.shape();
if b.shape()[0] != m {
return Err(LetoError::ShapeMismatch {
lhs: vec![m],
rhs: vec![b.shape()[0]],
});
}
if n == 0 {
return Ok(NnlsResult {
solution: Array1::zeros([0]),
residual_norm: norm_l2(b),
iterations: 0,
converged: true,
});
}
let mut x = Array1::from_elem([n], 0.0_f64);
let mut w = at_times(a, b);
let mut passive: Vec<usize> = Vec::with_capacity(n);
let mut is_passive = vec![false; n];
let mut residual = Array1::from_elem([m], 0.0_f64);
let mut a_passive = Array2::zeros([m, n]);
let mut iterations = 0;
let mut converged = false;
loop {
let (max_idx, max_val) = max_among_inactive(&w, &is_passive);
if max_val <= config.tolerance {
converged = true;
break;
}
if iterations >= config.max_iterations {
break;
}
passive.push(max_idx);
is_passive[max_idx] = true;
iterations += 1;
loop {
if passive.is_empty() {
break;
}
build_passive_matrix(a, &passive, &mut a_passive);
let k = passive.len();
let a_p_view = a_passive
.view()
.slice(&[(0, m, 1), (0, k, 1)])
.map_err(|e| LetoError::StorageError {
reason: e.to_string(),
})?;
let z = qr_decompose(&a_p_view)?.solve_least_squares(b)?;
let (_neg_idx, neg_val) = min_among(&z, passive.len());
if neg_val > -1e-12 {
for (local_idx, &global_idx) in passive.iter().enumerate() {
x[global_idx] = z[local_idx];
}
break;
}
let mut alpha = 1.0_f64;
let mut remove_mask: Vec<usize> = Vec::new();
for (local_idx, &global_idx) in passive.iter().enumerate() {
if z[local_idx] <= 0.0 {
let denom = x[global_idx] - z[local_idx];
if denom.abs() > 1e-15 {
let ratio = x[global_idx] / denom;
if ratio < alpha {
alpha = ratio;
}
}
remove_mask.push(local_idx);
}
}
for (local_idx, &global_idx) in passive.iter().enumerate() {
x[global_idx] += alpha * (z[local_idx] - x[global_idx]);
}
for &local_idx in remove_mask.iter().rev() {
let global_idx = passive[local_idx];
if x[global_idx].abs() < 1e-15 {
x[global_idx] = 0.0;
}
passive.remove(local_idx);
is_passive[global_idx] = false;
}
}
update_gradient(a, b, &x, &mut w, &mut residual);
}
let res_norm = residual_norm(a, b, &x);
Ok(NnlsResult {
solution: x,
residual_norm: res_norm,
iterations,
converged,
})
}
fn at_times(a: &ArrayView2<'_, f64>, v: &ArrayView1<'_, f64>) -> Array1<f64> {
let [m, n] = a.shape();
let mut result = Array1::zeros([n]);
for j in 0..n {
let mut dot = 0.0;
for i in 0..m {
dot += a[[i, j]] * v[i];
}
result[j] = dot;
}
result
}
fn max_among_inactive(w: &Array1<f64>, is_passive: &[bool]) -> (usize, f64) {
let n = w.shape()[0];
let mut best_idx = 0;
let mut best_val = f64::NEG_INFINITY;
for j in 0..n {
if is_passive[j] {
continue;
}
if w[j] > best_val {
best_val = w[j];
best_idx = j;
}
}
(best_idx, best_val)
}
fn min_among(z: &Array1<f64>, k: usize) -> (usize, f64) {
let mut best_idx = 0;
let mut best_val = z[0];
for j in 1..k {
if z[j] < best_val {
best_val = z[j];
best_idx = j;
}
}
(best_idx, best_val)
}
fn build_passive_matrix(a: &ArrayView2<'_, f64>, passive: &[usize], dest: &mut Array2<f64>) {
let m = a.shape()[0];
for (local_j, &global_j) in passive.iter().enumerate() {
for i in 0..m {
dest[[i, local_j]] = a[[i, global_j]];
}
}
}
fn update_gradient(
a: &ArrayView2<'_, f64>,
b: &ArrayView1<'_, f64>,
x: &Array1<f64>,
w: &mut Array1<f64>,
residual: &mut Array1<f64>,
) {
let [m, n] = a.shape();
for i in 0..m {
residual[i] = b[i] - dot_row(a, x, i);
}
for j in 0..n {
let mut dot = 0.0;
for i in 0..m {
dot += a[[i, j]] * residual[i];
}
w[j] = dot;
}
}
fn dot_row(a: &ArrayView2<'_, f64>, x: &Array1<f64>, i: usize) -> f64 {
let n = a.shape()[1];
let mut sum = 0.0;
for j in 0..n {
sum += a[[i, j]] * x[j];
}
sum
}
fn residual_norm(a: &ArrayView2<'_, f64>, b: &ArrayView1<'_, f64>, x: &Array1<f64>) -> f64 {
let m = a.shape()[0];
let mut sum_sq = 0.0;
for i in 0..m {
let diff = dot_row(a, x, i) - b[i];
sum_sq += diff * diff;
}
sum_sq.sqrt()
}
fn norm_l2(v: &ArrayView1<'_, f64>) -> f64 {
v.iter().map(|&x| x * x).sum::<f64>().sqrt()
}