Frequent Directions variants for matrix sketching
Matlab code for matrix sketching using Frequent Directions (FD) variants. Implements the original and fast FD algorithms (Liberty, 2013), a parameterization that varies smoothly between iterative SVD and FD (Desai et al, 2016), as well as a randomized variant suited for sparse inputs (Teng & Chu, 2017).
More information can be found here:
https://github.com/brian-lau/FrequentDirections
Issues/requests can be submitted here:
https://github.com/brian-lau/FrequentDirections/issues
Given an [n x d] matrix A, builds a [k x d] sketch B, where typically k << n. This object works for matrices that are stored completely in-memory as well as data streams (see examples).
To sketch an in-memory matrix:
k = 16; % sketch size
sketcher = FrequentDirections(k); % Initialize object
d = 64; % data dimensionality
data = randn(1000,d);
sketcher(data); % process samples
get(sketcher) % return sketch
sketcher.coverr(data) % covariance error
sketcher.projerr(data) % projection error
To sketch streaming data:
d = 512; % different data dimensionality
sketcher = FrequentDirections(32); % Initialize object
count = 0;
while count < 1000
data = randn(1,d); % random sample
sketcher(data); % consume sample
count = count + 1;
end
get(sketcher) % return sketch
References
Desai, A., Ghashami, M., & Phillips, J. M. (2016). Improved practical matrix sketching with guarantees. IEEE Transactions on Knowledge and Data Engineering, 28(7), 1678-1690.
Ghashami, M., Liberty, E., Phillips, J. M., & Woodruff, D. P. (2016). Frequent directions: Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5), 1762-1792.
Liberty, E. (2013). Simple and deterministic matrix sketching. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 581-588). ACM.
Teng, D. & Chu, D. (2017). Low-Rank approximation via sparse frequent directions. arXiv preprint arXiv:1705.07140.
引用格式
Brian Lau (2024). Frequent Directions variants for matrix sketching (https://github.com/brian-lau/FrequentDirections), GitHub. 检索来源 .
MATLAB 版本兼容性
平台兼容性
Windows macOS Linux类别
标签
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Examples
Testing
无法下载基于 GitHub 默认分支的版本
版本 | 已发布 | 发行说明 | |
---|---|---|---|
2.0.0.0 |
Added randomized FD variant of Teng & Chu (2017)
|
|