Понятие эскиза. Оценка частот элементов через эскизы.

• Алгоритм Чарикара-Чена-Фараха-Колтона. Для любого \(x\) выдает ответ в отрезке \([f_x - \varepsilon \cdot ||f||_2, f_x + \varepsilon \cdot ||f||_2]\) c вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-2} \log \delta^{-1} (\log n + \log m))\).
• Алгоритм Кормода-Муфукришнана. Для любого \(x\) выдает ответ в отрезке \([f_x, f_x + \varepsilon \cdot ||f||_1]\) с вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-1} \log \delta^{-1} (\log n + \log m))\).
• Алгоритм Алона-Матиаса-Сзегеди. Оценка момента \(F_2\) через эскиз. Выдает ответ с точность \(\pm \varepsilon ||f||_2\) c вероятностью \(1 - \delta\). Память: \(O(\varepsilon^{-2}\log \delta^{-1} (\log n + \log m))\)
• Алгоритм Вудраффа. Линейная регрессия при небольшом числе предикторов \(d\) на \(n\) наблюдениях. Выдает вектор коэффициентов \(\hat{x}\) такой, что \(||A\hat{x} - b||_2 \leq (1 + \varepsilon) \min_x ||Ax - b||_2\) с вероятностью \(1 - \delta\). Память: \(O(d^2 \varepsilon^{-1} \log \delta^{-1} \log (nd)\).
• Алгоритм Алона-Матиаса-Сзегеди. Оценка произвольного момента \(F_k\) при константе \(k \geq 1\). Память \(O(\varepsilon^{-2} \log \delta^{-1} n^{1 - \frac{1}{k}} (\log m + \log n))\).