Матрицы, тензоры и тропическая алгебра: линейная алгебра для поиска арбитража

Часть 4 серии «Сложные цепочки арбитража между фьючерсами и спотом»

Представьте себе огромный зал, где одновременно торгуют сотни менял. У каждого свой курс, свои комиссии, свои капризы. Вы стоите в центре этого зала с блокнотом, пытаясь найти маршрут обмена, который принесёт вам прибыль: доллары в евро, евро в йены, йены обратно в доллары — и на выходе больше, чем на входе. Запутаться легко. Но если записать все курсы в таблицу — в матрицу — внезапно хаос обретает структуру. Собственные значения этой матрицы скажут, есть ли арбитраж. Тропическая алгебра найдёт оптимальный маршрут. А тензорные разложения обнаружат паттерны, невидимые невооружённым глазом.

В этой статье мы проведём путешествие от простой таблицы обменных курсов до передовых методов многомерного анализа — и каждый шаг будет подкреплён реализацией на Rust.

Визуализация матрицы обменных курсов между криптовалютами: рёбра графа представляют торговые пары, а выделенный цикл — обнаруженную арбитражную возможность

1. Матрица обменных курсов: фундамент всего

1.1 От хаоса к таблице

Допустим, у нас есть n активов: BTC, ETH, USDT, SOL и так далее. Каждую пару можно обменять по определённому курсу. Матрица обменных курсов R — это таблица размером n × n, где элемент R[i][j] показывает, сколько единиц актива j мы получим за одну единицу актива i.

Свойства хорошо сформированной матрицы:

• Диагональ: R[i][i] = 1 — обмен актива на самого себя ничего не меняет
• Положительность: R[i][j] > 0 для всех пар
• Рецепрокальность (в идеальном рынке): R[i][j] * R[j][i] = 1

В Rust мы можем представить это с помощью nalgebra:

use nalgebra::DMatrix;

/// Строит матрицу обменных курсов из набора торговых пар
fn build_exchange_rate_matrix(
    assets: &[&str],
    rates: &[((usize, usize), f64)],
) -> DMatrix<f64> {
    let n = assets.len();
    let mut matrix = DMatrix::from_element(n, n, 0.0);

    // Диагональ: обмен на себя = 1
    for i in 0..n {
        matrix[(i, i)] = 1.0;
    }

    // Заполняем известные курсы
    for &((i, j), rate) in rates {
        matrix[(i, j)] = rate;
        // Рецепрокальный курс (если нет прямого)
        if matrix[(j, i)] == 0.0 {
            matrix[(j, i)] = 1.0 / rate;
        }
    }

    matrix
}

1.2 Условие отсутствия арбитража

Вот ключевая теорема, на которой строится всё остальное.

Теорема. Рынок свободен от арбитража тогда и только тогда, когда для любого цикла активов (i₁, i₂, ..., iₖ, i₁) произведение обменных курсов вдоль цикла равно единице:

R[i₁][i₂] * R[i₂][i₃] * ... * R[iₖ][i₁] = 1

Эквивалентная формулировка: матрица R свободна от арбитража тогда и только тогда, когда её ранг равен 1 (в мультипликативном смысле). Это значит, что существует вектор цен p = (p₁, p₂, ..., pₙ) такой, что:

R[i][j] = pⱼ / pᵢ   для всех i, j

Матрица R раскладывается как внешнее произведение R = (1/p) * pᵀ — и это матрица ранга 1. Если реальная матрица отклоняется от ранга 1 — значит, где-то прячется арбитраж.

Слева: идеальная матрица обменных курсов ранга 1 (без арбитража). Справа: реальная матрица с отклонениями — разница между ними указывает на арбитражные возможности

2. Метод собственных значений: арбитраж за O(n³)

2.1 Теорема Минга Ма

Один из самых элегантных подходов к обнаружению арбитража предложил Ming Ma в 2007 году. Идея гениально проста.

Теорема (Ming Ma). Пусть R — матрица обменных курсов n × n. Если рынок свободен от арбитража, то:

1. Наибольшее собственное значение λ_max = n
2. Все остальные собственные значения равны нулю
3. Соответствующий собственный вектор v представляет равновесные цены

Почему это работает? Матрица без арбитража имеет ранг 1, а её след (сумма диагональных элементов) равен n (потому что каждый R[i][i] = 1). Для матрицы ранга 1 единственное ненулевое собственное значение равно следу. Следовательно, λ_max = n.

Критерий арбитража: арбитраж существует тогда и только тогда, когда λ_max > n. Отклонение δ = λ_max - n количественно оценивает масштаб арбитражной возможности.

Интуиция здесь такая: представьте, что собственные значения — это «голоса» матрицы. В идеальном рынке все «голоса» сливаются в один хор (одно собственное значение n). Когда появляется арбитраж, гармония нарушается — хор начинает «фальшивить», и наибольшее собственное значение вырастает выше n.

2.2 Полный алгоритм обнаружения

use nalgebra::{DMatrix, DVector, SymmetricEigen};

/// Результат анализа арбитража методом собственных значений
#[derive(Debug)]
struct EigenArbitrageResult {
    /// Наибольшее собственное значение
    lambda_max: f64,
    /// Отклонение от n (мера арбитража)
    delta: f64,
    /// Равновесные цены (из собственного вектора)
    equilibrium_prices: DVector<f64>,
    /// Обнаружен ли арбитраж
    arbitrage_detected: bool,
    /// Матрица отклонений от равновесия
    deviations: DMatrix<f64>,
}

fn detect_arbitrage_eigenvalue(
    rate_matrix: &DMatrix<f64>,
    epsilon: f64,
) -> EigenArbitrageResult {
    let n = rate_matrix.nrows();

    // Для несимметричных матриц используем Schur-разложение
    let schur = rate_matrix.clone().schur();
    let eigenvalues = schur.eigenvalues().expect("Eigenvalue computation failed");

    // Находим наибольшее вещественное собственное значение
    let lambda_max = eigenvalues.iter()
        .map(|c| c.re)
        .fold(f64::NEG_INFINITY, f64::max);

    let delta = lambda_max - n as f64;

    // Извлекаем собственный вектор для lambda_max
    // Используем степенной метод для быстроты
    let eigenvector = power_iteration(rate_matrix, 100, 1e-10);

    // Нормализуем в вектор цен
    let sum: f64 = eigenvector.iter().sum();
    let equilibrium_prices = &eigenvector / sum;

    // Вычисляем отклонения: deviation[i][j] = R[i][j] - p[j]/p[i]
    let mut deviations = DMatrix::zeros(n, n);
    for i in 0..n {
        for j in 0..n {
            let fair_rate = equilibrium_prices[j] / equilibrium_prices[i];
            deviations[(i, j)] = rate_matrix[(i, j)] - fair_rate;
        }
    }

    EigenArbitrageResult {
        lambda_max,
        delta,
        equilibrium_prices,
        arbitrage_detected: delta > epsilon,
        deviations,
    }
}

/// Степенной метод: находит наибольшее собственное значение за O(n² * iterations)
fn power_iteration(
    matrix: &DMatrix<f64>,
    max_iter: usize,
    tol: f64,
) -> DVector<f64> {
    let n = matrix.nrows();
    let mut v = DVector::from_element(n, 1.0 / (n as f64).sqrt());

    for _ in 0..max_iter {
        let v_new = matrix * &v;
        let norm = v_new.norm();
        let v_normalized = &v_new / norm;

        if (&v_normalized - &v).norm() < tol {
            return v_normalized;
        }
        v = v_normalized;
    }
    v
}

Сложность: O(n³) для полного разложения, но степенной метод даёт O(n²) на итерацию — для матриц до 50 × 50 (типичный размер крипторынка) это работает за микросекунды.

Практические замечания:

• Метод собственных значений предполагает единую цену для каждой пары; бид-аск спреды не учитываются напрямую
• Комиссии включаем через модификацию курсов: R_eff[i][j] = R[i][j] * (1 - fee[i][j])
• Для крипторынков матрицу строим из мидпрайсов или лучших бидов/асков

3. Матричный логарифм: мост к Bellman-Ford

3.1 Из умножения — в сложение

Произведение курсов вдоль цикла — мультипликативная задача. Но если взять логарифм, умножение превращается в сложение, и мы попадаем в знакомую территорию теории графов.

Определение. Лог-матрица курсов L определяется как:

L[i][j] = -ln(R[i][j])

Арбитражный цикл (i₁, ..., iₖ, i₁) существует тогда и только тогда, когда:

L[i₁][i₂] + L[i₂][i₃] + ... + L[iₖ][i₁] < 0

Это в точности задача поиска отрицательного цикла в графе — классическая задача, которую решает алгоритм Беллмана-Форда.

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::bellman_ford;

/// Обнаружение арбитража через Bellman-Ford на лог-графе
fn detect_arbitrage_bellman_ford(
    rate_matrix: &DMatrix<f64>,
    asset_names: &[&str],
) -> Vec<Vec<usize>> {
    let n = rate_matrix.nrows();
    let mut graph = DiGraph::<&str, f64>::new();

    // Добавляем вершины
    let nodes: Vec<NodeIndex> = asset_names.iter()
        .map(|name| graph.add_node(name))
        .collect();

    // Добавляем рёбра с весами -ln(rate)
    for i in 0..n {
        for j in 0..n {
            if i != j && rate_matrix[(i, j)] > 0.0 {
                let weight = -(rate_matrix[(i, j)].ln());
                graph.add_edge(nodes[i], nodes[j], weight);
            }
        }
    }

    let mut negative_cycles = Vec::new();

    // Запускаем Bellman-Ford из каждой вершины
    for start in 0..n {
        match bellman_ford(&graph, nodes[start]) {
            Err(_) => {
                // Отрицательный цикл обнаружен!
                // Восстанавливаем цикл через predecessor chain
                // (упрощённая версия)
                negative_cycles.push(vec![start]);
            }
            Ok(_) => {}
        }
    }

    negative_cycles
}

3.2 Floyd-Warshall: все циклы за раз

Если нам нужны все арбитражные циклы одновременно, используем Floyd-Warshall:

/// Floyd-Warshall: находит ВСЕ арбитражные циклы
fn find_all_arbitrage_cycles(
    rate_matrix: &DMatrix<f64>,
) -> Vec<(usize, f64)> {
    let n = rate_matrix.nrows();

    // Строим лог-матрицу расстояний
    let mut dist = DMatrix::zeros(n, n);
    for i in 0..n {
        for j in 0..n {
            if rate_matrix[(i, j)] > 0.0 {
                dist[(i, j)] = -(rate_matrix[(i, j)].ln());
            } else {
                dist[(i, j)] = f64::INFINITY;
            }
        }
    }

    // Floyd-Warshall
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                let through_k = dist[(i, k)] + dist[(k, j)];
                if through_k < dist[(i, j)] {
                    dist[(i, j)] = through_k;
                }
            }
        }
    }

    // Проверяем диагональ: отрицательные значения = арбитраж
    let mut cycles = Vec::new();
    for i in 0..n {
        if dist[(i, i)] < -1e-10 {
            let profit_factor = (-dist[(i, i)]).exp();
            cycles.push((i, profit_factor));
        }
    }

    cycles
}

Floyd-Warshall имеет сложность O(n³), зато находит все циклы одновременно и даёт точную величину прибыли каждого цикла.

Граф с весами -ln(rate): отрицательные циклы (выделены красным) соответствуют арбитражным возможностям. Bellman-Ford находит один цикл за O(VE), Floyd-Warshall находит все за O(V³)*

4. Тропическая (Max-Plus) алгебра: самый элегантный метод

4.1 Когда сложение становится максимумом

Это, пожалуй, самая красивая находка в нашем исследовании. Тропическая алгебра — это алгебраическая система, в которой привычные операции переопределены:

• «Сложение»: a ⊕ b = max(a, b)
• «Умножение»: a ⊗ b = a + b

Звучит странно? Представьте себе путешественника, который ищет самый длинный маршрут в сети дорог. Обычная алгебра ему не поможет — ведь кратчайший путь и длиннейший путь требуют разных операций. Но если заменить «+» на «max», а «×» на «+», матричное умножение автоматически ищет путь с максимальной суммой весов. Именно это нужно для поиска самого прибыльного арбитражного цикла.

4.2 Тропическое собственное значение и арбитраж

Берём лог-матрицу курсов L[i][j] = ln(R[i][j]) (обратите внимание: здесь логарифм без минуса, в отличие от Bellman-Ford). Вычисляем тропическое собственное значение λ матрицы L.

Теорема. λ > 0 тогда и только тогда, когда существует арбитраж. При этом exp(λ) — это множитель прибыли наилучшего цикла.

Почему это элегантнее Bellman-Ford? Потому что тропическое собственное значение — это единственное число, которое мгновенно отвечает на вопрос «есть ли арбитраж?» и одновременно показывает его масштаб. Никакого перебора циклов, никакого восстановления путей — просто число.

4.3 Алгоритм: тропические степени матрицы

/// Тропическое (max-plus) умножение матриц
fn tropical_matmul(a: &DMatrix<f64>, b: &DMatrix<f64>) -> DMatrix<f64> {
    let n = a.nrows();
    let m = b.ncols();
    let k = a.ncols();
    let mut result = DMatrix::from_element(n, m, f64::NEG_INFINITY);

    for i in 0..n {
        for j in 0..m {
            for l in 0..k {
                // Тропическое умножение: max вместо sum, + вместо *
                let val = a[(i, l)] + b[(l, j)];
                if val > result[(i, j)] {
                    result[(i, j)] = val;
                }
            }
        }
    }

    result
}

/// Поиск арбитража через тропические степени матрицы
fn tropical_arbitrage_detection(
    rate_matrix: &DMatrix<f64>,
    max_cycle_length: usize,
) -> Vec<TropicalArbitrageResult> {
    let n = rate_matrix.nrows();
    let mut results = Vec::new();

    // Строим лог-матрицу (без минуса!)
    let mut log_matrix = DMatrix::from_element(n, n, f64::NEG_INFINITY);
    for i in 0..n {
        for j in 0..n {
            if rate_matrix[(i, j)] > 0.0 {
                log_matrix[(i, j)] = rate_matrix[(i, j)].ln();
            }
        }
    }

    // Вычисляем тропические степени L^(k) для k = 2..max_cycle_length
    let mut power = log_matrix.clone();

    for k in 2..=max_cycle_length {
        power = tropical_matmul(&power, &log_matrix);

        // Проверяем диагональ: L^(k)[i][i] > 0 => k-арбитраж через i
        for i in 0..n {
            if power[(i, i)] > 1e-10 {
                results.push(TropicalArbitrageResult {
                    start_asset: i,
                    cycle_length: k,
                    log_profit: power[(i, i)],
                    profit_factor: power[(i, i)].exp(),
                });
            }
        }
    }

    results
}

#[derive(Debug)]
struct TropicalArbitrageResult {
    start_asset: usize,
    cycle_length: usize,
    log_profit: f64,
    profit_factor: f64,
}

Сложность: O(n³ * k_max), но с тропическим быстрым возведением в степень (squaring) можно довести до O(n³ * log(k_max)).

4.4 Аналогия: тропическая алгебра как GPS для арбитража

Представьте GPS-навигатор, который ищет маршрут. Обычный навигатор минимизирует время. Наш «тропический навигатор» максимизирует прибыль. Тропическое умножение матрицы — это один «шаг» навигации через все возможные промежуточные точки. Диагональный элемент L^(k)[i][i] — это лучшая прибыль при возвращении в актив i за ровно k шагов. Если эта прибыль положительна — мы нашли арбитраж.

Что особенно красиво: тропическая алгебра автоматически выбирает оптимальную длину цикла. Не нужно перебирать все возможные тройки, четвёрки, пятёрки активов — тропические степени делают это за нас.

Тропическое умножение матриц: вместо суммы произведений берётся максимум сумм. Диагональ тропической степени L^(k) показывает лучший k-шаговый арбитражный цикл для каждого актива

5. Линейное программирование: оптимальный размер сделок

5.1 LP-формулировка

Мы нашли арбитражный цикл — отлично. Но сколько денег в него вложить? Как распределить капитал между несколькими одновременными возможностями? Это задача линейного программирования.

Дано:

• n активов, обменные курсы R[i][j]
• Комиссии f[i][j] на каждую конвертацию
• Начальный капитал C в базовом активе (например, USDT)
• Ограничения по глубине стакана max_vol[i][j]

Переменные решения: x[i][j] = объём актива i, конвертируемый в актив j.

максимизировать:  Σⱼ x[j,base] * R[j,base] * (1 - f[j,base]) - C

при ограничениях:
  // Сохранение потока для каждого не-базового актива k:
  Σᵢ x[i,k] * R[i,k] * (1 - f[i,k]) = Σⱼ x[k,j]   для всех k ≠ base

  // Ограничение на отток базового актива:
  Σⱼ x[base,j] ≤ C

  // Неотрицательность:
  x[i][j] ≥ 0

  // Ограничения по ёмкости (глубина стакана):
  x[i][j] ≤ max_vol[i][j]

5.2 Двойственность LP и условие no-arbitrage

Двойственность линейного программирования даёт глубокую связь с теорией безарбитражности.

Прямая задача (обнаружение арбитража):

max  cᵀx
s.t. Ax ≤ 0,  x ≥ 0

Двойственная задача (риск-нейтральное ценообразование):

min  0
s.t. Aᵀy ≥ c,  y ≥ 0

Ключевая теорема: арбитраж отсутствует тогда и только тогда, когда двойственная задача допустима. Двойственные переменные y — это риск-нейтральные вероятности (или цены состояний). Существование положительных цен состояний, совместимых с рыночными ценами, эквивалентно отсутствию арбитража.

Для крипто-арбитража это означает:

• Допустимость прямой задачи + неограниченная целевая функция = арбитраж существует
• Допустимость двойственной задачи = арбитража нет, двойственные переменные дают справедливые цены
• «Зазор» между прямой и двойственной задачами измеряет масштаб арбитража

5.3 Сетевая формулировка (Network Flow)

Многоногий арбитраж естественно отображается в задачу сетевого потока минимальной стоимости:

• Узлы: активы (валюты/токены)
• Дуги: торговые пары с курсами обмена
• Поток: объём стоимости, передаваемый по каждой дуге
• Стоимости: отрицательные лог-курсы (с учётом комиссий)
• Ёмкости: глубина стакана

use clarabel::algebra::*;
use clarabel::solver::*;

/// Упрощённая LP-формулировка оптимального арбитражного размера
/// через задачу сетевого потока
fn solve_arbitrage_lp(
    n_assets: usize,
    rates: &[(usize, usize, f64)],  // (from, to, effective_rate)
    capacities: &[(usize, usize, f64)],  // (from, to, max_volume)
    capital: f64,
    base_asset: usize,
) -> Vec<f64> {
    // Количество переменных = количество торговых пар
    let n_vars = rates.len();

    // Целевая функция: максимизируем входящий поток в base_asset
    // (для Clarabel: минимизируем отрицательный поток)
    let mut q = vec![0.0; n_vars];
    for (idx, &(from, to, rate)) in rates.iter().enumerate() {
        if to == base_asset {
            q[idx] = -rate;  // Минимизируем => максимизируем прибыль
        }
    }

    // Ограничения потока: для каждого не-базового актива
    // входящий поток = исходящий поток
    // ... (формируем разреженную матрицу ограничений)

    // Решаем LP через interior-point solver
    // Типичное время решения: < 1 мс для n_assets < 100

    vec![0.0; n_vars] // Заглушка — реальная реализация через Clarabel
}

Для DEX-арбитража сетевая формулировка естественно расширяется на несколько пулов для одной торговой пары (разные DEX), мультихоп-маршруты (ETH -> USDC -> DAI -> ETH) и ограничения ликвидности каждого пула.

Сетевая модель арбитража: узлы — активы, дуги — торговые пары с ёмкостями (глубина стакана). Оптимальный поток находится методом interior-point за субмиллисекундное время

6. PCA и факторные модели: статистический арбитраж

6.1 Факторная декомпозиция доходностей

Переходим от детерминированного арбитража (прямые ценовые расхождения) к статистическому арбитражу — поиску систематических отклонений от факторной модели.

Метод главных компонент (PCA) разлагает доходности активов на систематические факторы и идиосинкратические остатки:

rᵢ(t) = αᵢ + Σₖ βᵢₖ * Fₖ(t) + εᵢ(t)

где Fₖ(t) — k-й фактор (главная компонента), βᵢₖ — нагрузка актива i на фактор k, а εᵢ(t) — остаток, который и является арбитражным сигналом.

use ndarray::{Array1, Array2, Axis};
use ndarray_linalg::{Eigh, UPLO};

/// PCA-разложение доходностей для статистического арбитража
struct PcaArbitrage {
    /// Факторные нагрузки (n_assets × n_factors)
    loadings: Array2<f64>,
    /// Собственные значения (дисперсия каждого фактора)
    eigenvalues: Array1<f64>,
    /// Количество факторов
    n_factors: usize,
}

impl PcaArbitrage {
    fn fit(returns: &Array2<f64>, n_factors: usize) -> Self {
        let (n_time, n_assets) = returns.dim();

        // 1. Стандартизация
        let means = returns.mean_axis(Axis(0)).unwrap();
        let stds = returns.std_axis(Axis(0), 0.0);
        let standardized = (returns - &means) / &stds;

        // 2. Ковариационная матрица
        let cov = standardized.t().dot(&standardized) / n_time as f64;

        // 3. Собственное разложение
        let (eigenvalues, eigenvectors) = cov.eigh(UPLO::Upper).unwrap();

        // Берём top-K факторов (собственные значения в порядке возрастания)
        let loadings = eigenvectors
            .slice(ndarray::s![.., (n_assets - n_factors)..])
            .to_owned();

        let top_eigenvalues = eigenvalues
            .slice(ndarray::s![(n_assets - n_factors)..])
            .to_owned();

        PcaArbitrage {
            loadings,
            eigenvalues: top_eigenvalues,
            n_factors,
        }
    }

    /// Вычисляет z-score остатков для каждого актива
    fn compute_signals(
        &self,
        returns: &Array2<f64>,
    ) -> Array1<f64> {
        let means = returns.mean_axis(Axis(0)).unwrap();
        let stds = returns.std_axis(Axis(0), 0.0);
        let standardized = (returns - &means) / &stds;

        // Проецируем на факторы
        let factors = standardized.dot(&self.loadings);

        // Реконструируем
        let reconstructed = factors.dot(&self.loadings.t());

        // Остатки
        let residuals = &standardized - &reconstructed;

        // Z-scores последней строки (текущий момент)
        let last_residuals = residuals.row(residuals.nrows() - 1);
        let residual_std = residuals.std_axis(Axis(0), 0.0);

        &last_residuals.to_owned() / &residual_std
    }
}

Правила торговли просты: если z-score остатка zᵢ > +порог — актив переоценён относительно факторов, открываем SHORT. Если zᵢ < -порог — актив недооценён, открываем LONG.

6.2 Теория случайных матриц: фильтрация шума

Ключевой вопрос: сколько факторов оставить? Если взять слишком мало — потеряем сигнал. Слишком много — включим шум. Ответ даёт теория случайных матриц (RMT) и распределение Марченко-Пастура.

Распределение Марченко-Пастура описывает спектр собственных значений случайной ковариационной матрицы. Для матрицы T × n с i.i.d. элементами:

λ₊ = σ² * (1 + √(n/T))²    (верхняя граница шума)
λ₋ = σ² * (1 - √(n/T))²    (нижняя граница шума)

Собственные значения внутри [λ₋, λ₊] — это шум. Собственные значения выше λ₊ несут настоящий сигнал.

/// Очистка ковариационной матрицы по Марченко-Пастуру
fn denoise_covariance_rmt(
    cov: &Array2<f64>,
    n_observations: usize,
) -> Array2<f64> {
    let n = cov.dim().0;
    let gamma = n as f64 / n_observations as f64;

    // Границы Марченко-Пастура
    let lambda_plus = (1.0 + gamma.sqrt()).powi(2);
    let lambda_minus = (1.0 - gamma.sqrt()).powi(2);

    // Собственное разложение
    let (eigenvalues, eigenvectors) = cov.eigh(UPLO::Upper).unwrap();

    // Очистка: шумовые значения заменяем средним
    let noise_eigenvalues: Vec<f64> = eigenvalues.iter()
        .filter(|&&l| l <= lambda_plus)
        .copied()
        .collect();

    let noise_mean = if noise_eigenvalues.is_empty() {
        0.0
    } else {
        noise_eigenvalues.iter().sum::<f64>() / noise_eigenvalues.len() as f64
    };

    let mut clean_eigenvalues = eigenvalues.clone();
    for val in clean_eigenvalues.iter_mut() {
        if *val <= lambda_plus {
            *val = noise_mean;
        }
    }

    // Восстанавливаем очищенную ковариационную матрицу
    let diag = Array2::from_diag(&clean_eigenvalues);
    let result = eigenvectors.dot(&diag).dot(&eigenvectors.t());

    // Нормализуем след
    let scale = cov.diag().sum() / result.diag().sum();
    result * scale
}

Влияние на арбитраж: при 100 активах и 250 днях данных γ = 0.4 — это значит, что около 40% собственных значений — чистый шум. Без RMT-очистки мы будем генерировать ложные арбитражные сигналы на основе случайных корреляций.

Гистограмма собственных значений: область внутри границ Марченко-Пастура (серая) — шум, значения выше верхней границы (красные) — настоящие факторы рынка

6.3 Остаточная альфа как сигнал арбитража

После удаления систематических факторов через PCA остаток εᵢ(t) моделируется как процесс Орнштейна-Уленбека (mean-reverting):

d(εᵢ) = κᵢ * (μᵢ - εᵢ) * dt + σᵢ * dWᵢ

где κᵢ — скорость возврата к среднему, μᵢ — долгосрочное среднее (обычно 0), σᵢ — волатильность остатка.

Оптимальные пороги входа/выхода (из решения OU-процесса):

Вход (LONG):  εᵢ < μᵢ - σᵢ * √(2 * ln(κᵢ / c))
Вход (SHORT): εᵢ > μᵢ + σᵢ * √(2 * ln(κᵢ / c))
Выход:        |εᵢ - μᵢ| < δ

где c — транзакционные издержки. Портфель строится как wᵢ = -zᵢ / Σ|zⱼ| — отрицательные z-scores (недооценённые) получают положительные веса и наоборот. Портфель нейтрален к доллару и факторам по конструкции.

7. Asset Embeddings (Asset2Vec): активы как векторы

7.1 Идея

Вдохновлённый Word2Vec из NLP, подход Asset2Vec отображает финансовые инструменты в непрерывное векторное пространство размерности d (обычно 4-64). В этом пространстве близкие векторы означают экономически схожие активы.

Метод обучения на основе доходностей:

Для каждого временного окна t:
  1. Вычисляем попарные корреляции доходностей C_t[i][j]
  2. Создаём положительные пары: (i,j) при C_t[i][j] > порог
  3. Создаём отрицательные пары: (i,j) при C_t[i][j] < -порог
  4. Обучаем эмбеддинг контрастивной функцией потерь

7.2 Метрики расстояния для обнаружения мисприсинга

Имея эмбеддинги, мы конструируем арбитражный сигнал:

signal(i, j, t) = [cos(vᵢ, vⱼ) - (price_ratio(i,j,t) / price_ratio_MA(i,j))] / vol(price_ratio(i,j))

Высокая косинусная схожесть в сочетании с большим ценовым отклонением (нормализованным по волатильности) генерирует сильный арбитражный сигнал: активы «должны» стоить похоже, но сейчас расходятся.

/// Расчёт арбитражного сигнала на основе эмбеддингов
fn embedding_arbitrage_signal(
    embedding_i: &[f64],
    embedding_j: &[f64],
    current_price_ratio: f64,
    ma_price_ratio: f64,
    price_ratio_vol: f64,
) -> f64 {
    let cosine_sim = cosine_similarity(embedding_i, embedding_j);
    let price_deviation = (current_price_ratio / ma_price_ratio) - 1.0;

    // Сильный сигнал: активы похожи (cos ~ 1), но цены разошлись
    cosine_sim * price_deviation / price_ratio_vol
}

fn cosine_similarity(a: &[f64], b: &[f64]) -> f64 {
    let dot: f64 = a.iter().zip(b).map(|(x, y)| x * y).sum();
    let norm_a: f64 = a.iter().map(|x| x * x).sum::<f64>().sqrt();
    let norm_b: f64 = b.iter().map(|x| x * x).sum::<f64>().sqrt();
    dot / (norm_a * norm_b)
}

Результаты исследования Gabaix, Koijen и Richmond (2024) показывают, что 4-мерное вложение объясняет более 50% вариации в относительных оценках активов — по сравнению с 15% для стандартных характеристик.

8. Тензорные методы: третье измерение арбитража

8.1 3D-тензор рынка

Криптовалютный арбитраж включает несколько измерений одновременно. Матрица курсов — это лишь 2D-срез. Реальная картина — тензор:

T(a, e, i) = цена/курс для актива a на бирже e для инструмента i

Измерения:

• Мода 1 (Активы): BTC, ETH, SOL, ... (n_a активов)
• Мода 2 (Биржи): Binance, Kraken, Coinbase, ... (n_e бирж)
• Мода 3 (Типы инструментов): Spot, Perpetual, Futures-Q1, Options, ... (n_i типов)

Это тензор 3-го порядка T ∈ ℝ^{n_a × n_e × n_i}. При добавлении временной размерности получаем 4D-тензор T(a, e, i, t).

8.2 CP-разложение (CANDECOMP/PARAFAC)

CP-разложение факторизует тензор в сумму тензоров ранга 1:

T ≈ Σᵣ λᵣ * (aᵣ ⊗ bᵣ ⊗ cᵣ)

где aᵣ — вектор «факторов активов», bᵣ — вектор «факторов бирж», cᵣ — вектор «факторов инструментов», и ⊗ — внешнее произведение.

Применение к арбитражу: каждая компонента r представляет «фактор», объясняющий скоррелированные движения цен. Остаток T - T_approx выявляет аномалии: если T(BTC, Binance, Spot) - T_approx(BTC, Binance, Spot) велик, BTC spot на Binance неправильно оценён относительно общей факторной структуры.

use ndarray::Array3;

/// CP-разложение тензора методом ALS (Alternating Least Squares)
struct CpDecomposition {
    /// Факторы активов (n_assets × rank)
    asset_factors: Array2<f64>,
    /// Факторы бирж (n_exchanges × rank)
    exchange_factors: Array2<f64>,
    /// Факторы инструментов (n_instruments × rank)
    instrument_factors: Array2<f64>,
    /// Веса компонент
    weights: Array1<f64>,
}

impl CpDecomposition {
    /// ALS: фиксируем две моды, оптимизируем третью
    fn fit(
        tensor: &Array3<f64>,
        rank: usize,
        max_iter: usize,
        tol: f64,
    ) -> Self {
        let (n_a, n_e, n_i) = tensor.dim();

        // Инициализация случайными значениями
        let mut a = Array2::<f64>::from_shape_fn(
            (n_a, rank), |_| rand::random::<f64>()
        );
        let mut b = Array2::<f64>::from_shape_fn(
            (n_e, rank), |_| rand::random::<f64>()
        );
        let mut c = Array2::<f64>::from_shape_fn(
            (n_i, rank), |_| rand::random::<f64>()
        );

        for _iter in 0..max_iter {
            // Шаг 1: Фиксируем B, C; решаем для A
            // A = T_(1) * (C ⊙ B) * ((CᵀC ⊙ BᵀB))⁻¹
            // (где ⊙ — Khatri-Rao произведение)

            // Шаг 2: Фиксируем A, C; решаем для B
            // Шаг 3: Фиксируем A, B; решаем для C

            // Нормализация столбцов
            // ... (полная реализация опущена для краткости)
        }

        let weights = Array1::ones(rank);

        CpDecomposition {
            asset_factors: a,
            exchange_factors: b,
            instrument_factors: c,
            weights,
        }
    }

    /// Находит аномалии: большой остаток = потенциальный арбитраж
    fn find_anomalies(
        &self,
        tensor: &Array3<f64>,
        threshold: f64,
    ) -> Vec<(usize, usize, usize, f64)> {
        let (n_a, n_e, n_i) = tensor.dim();
        let mut anomalies = Vec::new();

        for a in 0..n_a {
            for e in 0..n_e {
                for i in 0..n_i {
                    // Реконструированное значение
                    let mut reconstructed = 0.0;
                    for r in 0..self.weights.len() {
                        reconstructed += self.weights[r]
                            * self.asset_factors[(a, r)]
                            * self.exchange_factors[(e, r)]
                            * self.instrument_factors[(i, r)];
                    }

                    let residual = tensor[(a, e, i)] - reconstructed;
                    if residual.abs() > threshold {
                        anomalies.push((a, e, i, residual));
                    }
                }
            }
        }

        // Сортируем по абсолютному отклонению
        anomalies.sort_by(|x, y| {
            y.3.abs().partial_cmp(&x.3.abs()).unwrap()
        });

        anomalies
    }
}

8.3 Tucker-разложение

Tucker-разложение обобщает CP, допуская ядерный тензор (core tensor):

T ≈ G ×₁ A ×₂ B ×₃ C

где G ∈ ℝ^{R₁ × R₂ × R₃} — ядерный тензор, а A, B, C — факторные матрицы. В отличие от CP, Tucker позволяет разные ранги по каждой моде и фиксирует кросс-модовые взаимодействия через ядерный тензор.

Для крипто-арбитража это важно: взаимодействия между активами, биржами и типами инструментов не обязательно имеют одинаковую «сложность». Может быть 5 активных факторов, но всего 3 биржевых и 2 инструментных.

3D-тензор рынка T(актив, биржа, инструмент) и его CP-разложение: каждая компонента r — это «фактор», объясняющий скоррелированные движения. Аномалии в остатке — арбитражные сигналы

9. Выпуклая оптимизация: арбитраж с контролем риска

9.1 SOCP: коническое программирование второго порядка

Линейное программирование (раздел 5) не умеет учитывать квадратичные ограничения на риск. SOCP (Second-Order Cone Programming) расширяет LP конусными ограничениями второго порядка:

максимизировать:  expected_profit(x)

при ограничениях:
  // Ограничение на риск (волатильность):
  ||Σ^{1/2} * x||₂ ≤ risk_budget

  // Максимальные позиции:
  |xᵢ| ≤ max_position_i

  // Ограничение нетто-экспозиции:
  |1ᵀx| ≤ max_net_exposure

  // Ограничение транзакционных издержек:
  Σᵢ fee_i * |xᵢ| ≤ max_cost

Ограничение ||Σ^{1/2} * x||₂ ≤ σ_max — это коническое ограничение второго порядка, что делает задачу разрешимой SOCP-солверами за полиномиальное время O(n^3.5).

9.2 DEX-арбитраж как выпуклая задача

В DeFi маркет-мейкеры с постоянной функцией (CFMM) удовлетворяют общему понятию выпуклости. Для Uniswap v2: φ(Rₓ, Rᵧ) = Rₓ * Rᵧ = const.

Задача оптимальной маршрутизации:

максимизировать:  суммарный выход токенов

при ограничениях:
  // Сохранение потока:
  Σ (выходы из пула j для токена i) - Σ (входы в пул j для токена i) ≥ 0

  // Инвариант CFMM:
  φⱼ(Rⱼ + γⱼΔⱼ - Λⱼ) ≥ φⱼ(Rⱼ)

Ключевой результат (Angeris et al., 2021): без учёта фиксированных газовых расходов это выпуклая задача, разрешимая за полиномиальное время. Оптимальный арбитраж — частный случай (максимизация выхода одного токена, начиная с того же токена).

9.3 Робастная оптимизация

Рыночные условия меняются быстро. Арбитражное решение должно быть устойчиво к неопределённости в курсах (проскальзывание, задержки), комиссиях (волатильность газа) и глубине стакана.

максимизировать:  rᵀx - ρ * ||x||₂

при стандартных ограничениях потока и ёмкости

Штрафной терм ρ * ||x||₂ автоматически уменьшает размер позиций при высокой неопределённости — это естественный компромисс между доходностью и риском.

use clarabel::algebra::CscMatrix;
use clarabel::solver::{DefaultSettings, DefaultSolver, SolverStatus};

/// SOCP для оптимального размера арбитража с контролем риска
fn solve_risk_constrained_arbitrage(
    expected_returns: &[f64],       // ожидаемая доходность каждой ноги
    cov_sqrt: &Array2<f64>,         // Σ^{1/2}
    risk_budget: f64,               // максимальная волатильность
    max_positions: &[f64],          // ограничения на позиции
) -> Vec<f64> {
    let n = expected_returns.len();

    // Формируем задачу SOCP для Clarabel:
    // min -expected_returns^T * x
    // s.t. ||cov_sqrt * x||_2 <= risk_budget   (SOC constraint)
    //      -max_pos <= x <= max_pos              (box constraints)

    let settings = DefaultSettings {
        verbose: false,
        ..DefaultSettings::default()
    };

    // ... (формирование разреженных матриц для Clarabel)
    // Clarabel решает за O(n^3.5), типично 10-30 итераций

    vec![0.0; n] // Заглушка — реальная реализация через Clarabel API
}

Слева: выпуклая область допустимых решений SOCP с коническим ограничением на риск. Справа: оптимальный маршрут через несколько пулов DEX, найденный как решение выпуклой задачи оптимизации

10. Экосистема Rust: практический инструментарий

10.1 Основные крейты линейной алгебры

Для реализации всех описанных методов на Rust мы рекомендуем следующий стек:

nalgebra — чистый Rust, высокопроизводительная линейная алгебра. Поддерживает матрицы как статического, так и динамического размера. Разложения: SVD, QR, LU, Cholesky, собственное разложение, Schur. Оптимизирован через SIMD. Лучший выбор для матриц обменных курсов (фиксированный размер, до 100 × 100).

ndarray — N-мерные массивы в стиле NumPy. Динамическая размерность, broadcasting, slicing. Идеален для больших массивов данных: временные ряды, факторные матрицы, ковариационные матрицы. В паре с ndarray-linalg получаем LAPACK-backed разложения.

faer — современная библиотека линейной алгебры на чистом Rust с фокусом на корректность и производительность. Плотные и разреженные матрицы. SVD, собственное разложение, Cholesky, QR, LU. Включает faer-sparse для разреженных задач. Активно развивается и часто превосходит LAPACK на малых/средних матрицах.

10.2 Солверы оптимизации

Clarabel.rs — interior-point солвер для выпуклой конической оптимизации. Поддерживает LP, QP, SOCP, SDP, экспоненциальные конусы, степенные конусы. Чистый Rust, лицензия Apache 2.0. Разработан Oxford Control Group. Идеален для SOCP-задач размера арбитража с контролем риска.

good_lp — удобный интерфейс моделирования LP/MIP с несколькими бэкендами (включая Clarabel для чистого Rust). Отличный выбор для быстрого прототипирования LP-формулировок.

minilp — лёгкий чистый Rust LP-солвер для малых-средних задач, когда важна минимальность зависимостей.

10.3 Графы и разреженные матрицы

petgraph — структуры данных и алгоритмы для графов. Включает реализации Bellman-Ford и Floyd-Warshall — именно то, что нужно для обнаружения арбитражных циклов на лог-графе курсов.

sprs — разреженные матрицы в форматах CSR/CSC. Разреженное матрично-векторное умножение. Необходим для больших разреженных матриц обменных курсов и задач сетевого потока.

10.4 Рекомендуемая архитектура

                    ┌───────────────────┐
                    │   Data Ingestion  │
                    │  (Orderbooks,     │
                    │   Prices, Fees)   │
                    └────────┬──────────┘
                             │
                    ┌────────▼──────────┐
                    │  Exchange Rate    │
                    │  Matrix Builder   │
                    │  (nalgebra)       │
                    └────────┬──────────┘
                             │
              ┌──────────────┼──────────────┐
              │              │              │
     ┌────────▼──────┐ ┌────▼───────┐ ┌────▼────────┐
     │  Eigenvalue   │ │ Bellman-   │ │  Tropical   │
     │  Arbitrage    │ │ Ford Cycle │ │  Max-Plus   │
     │  Detector     │ │ Detection  │ │  Iteration  │
     │ (nalgebra/    │ │ (petgraph) │ │  (custom)   │
     │  faer)        │ │            │ │             │
     └────────┬──────┘ └────┬───────┘ └────┬────────┘
              │              │              │
              └──────────────┼──────────────┘
                             │
                    ┌────────▼──────────┐
                    │  Opportunity      │
                    │  Ranker & Filter  │
                    │  (PCA/RMT:       │
                    │   ndarray + faer) │
                    └────────┬──────────┘
                             │
                    ┌────────▼──────────┐
                    │  Optimal Sizing   │
                    │  (Clarabel        │
                    │   SOCP/LP)        │
                    └────────┬──────────┘
                             │
                    ┌────────▼──────────┐
                    │ Execution Engine  │
                    └───────────────────┘

10.5 Целевые показатели производительности

При реализации на Rust с SIMD-оптимизацией ожидаемые задержки:

Все показатели вписываются в требования субмиллисекундной торговли для большинства криптовалютных бирж, а более тяжёлые вычисления (PCA, тензоры) выполняются на фоновом потоке с периодом обновления порядка секунд.

Заключение

Мы прошли путь от простой таблицы обменных курсов до тропической алгебры, тензорных разложений и выпуклой оптимизации. Каждый метод решает свою часть задачи:

1. Матрица обменных курсов и собственные значения — быстрая проверка «есть ли арбитраж вообще?» за O(n²) со степенным методом
2. Матричный логарифм + Bellman-Ford — конкретные циклы и маршруты
3. Тропическая алгебра — самый элегантный метод, дающий единственное число-ответ и автоматически оптимизирующий длину цикла
4. Линейное программирование — оптимальные размеры сделок с учётом ёмкостей
5. PCA + RMT — статистический арбитраж на основе факторных моделей с фильтрацией шума
6. Asset Embeddings — обнаружение мисприсинга в векторном пространстве
7. Тензорные методы — многомерные паттерны (актив × биржа × инструмент)
8. SOCP — оптимальный размер с контролем риска

Все методы реализуемы на Rust с помощью зрелых крейтов (nalgebra, ndarray, faer, Clarabel, petgraph), обеспечивающих производительность уровня C/C++ без жертв в безопасности памяти.

В следующей части серии мы рассмотрим методы машинного обучения для прогнозирования арбитражных возможностей и адаптивные стратегии исполнения.

Полезные ссылки

• nalgebra — линейная алгебра для Rust
• ndarray — N-мерные массивы
• faer — современная линейная алгебра на Rust
• Clarabel.rs — конический оптимизационный солвер
• petgraph — графы и алгоритмы
• good_lp — моделирование LP на Rust
• sprs — разреженные матрицы

Цитирование

@software{soloviov2026vectormatrix,
  author = {Soloviov, Eugen},
  title = {Матрицы, тензоры и тропическая алгебра: линейная алгебра для поиска арбитража},
  year = {2026},
  url = {https://marketmaker.cc/ru/blog/post/complex-arbitrage-vector-matrix},
  version = {0.1.0},
  description = {Как матрица обменных курсов, собственные значения, тропическая алгебра и тензорные разложения превращают хаос криптовалютных бирж в чёткие арбитражные сигналы}
}

Источники

1. Ma, M. (2007). "Identifying Foreign Exchange Arbitrage Opportunities through Matrix Approach." SSRN.
2. Ma, M. (2006). "A Matrix Approach to Asset Pricing in Foreign Exchange Market." SSRN.
3. Mason, B. (2010). "Tropical algebra, graph theory, & foreign exchange arbitrage." JMU Honors Program.
4. Angeris, G. et al. (2021). "Constant Function Market Makers: Multi-Asset Trades via Convex Optimization." arXiv.
5. Avellaneda, M., Lee, J. (2010). "Statistical arbitrage in the US equities market." Quantitative Finance.
6. Bun, J., Bouchaud, J.P., Potters, M. (2017). "Cleaning large Correlation Matrices: Tools from Random Matrix Theory." Physics Reports.
7. Gabaix, X., Koijen, R., Richmond, R. (2024). "Asset Embeddings." Working Paper.
8. Ghaoui, L., Oks, M., Oustry, F. (2003). "Worst-Case Value-At-Risk and Robust Portfolio Optimization." Operations Research.
9. Luo, Y. et al. (2025). "RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage." VLDB.
10. Kolda, T.G., Bader, B.W. (2009). "Tensor Decompositions and Applications." SIAM Review.
11. Marchenko, V., Pastur, L. (1967). "Distribution of eigenvalues for some sets of random matrices." Mathematics of the USSR-Sbornik.
12. Varolgunes, U. et al. (2023). "NMTucker: Non-linear Matryoshka Tucker Decomposition." ACM ICAIF.
13. Chen, S., Zhou, Q. (2021). "Robust Portfolio Optimization meets Arbitrage Pricing Theory." European Journal of Operational Research.
14. Stevens Institute — Foreign Exchange Arbitrage (Eigenvalue method tutorial)
15. Chua, Y. — Detecting Arbitrage in Foreign Exchange Markets (Python)
16. Autry, E. — Bellman-Ford and Arbitrage (Lecture notes)
17. Stanford CME241 — Arbitrage and Completeness (LP formulation)
18. Hudson & Thames — PCA Approach in ArbitrageLab
19. Bain Capital Crypto — Optimal Routing for Constant Function Market Makers
20. Portfolio Optimizer — Correlation Matrices Denoising: Results from Random Matrix Theory