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

• Алгоритм Чарикара-Чена-Фараха-Колтона. Для любого $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))$.