
Numerical Linear Algebra in the Sliding Window Model
We initiate the study of numerical linear algebra in the sliding window ...
read it

Efficient Symmetric Norm Regression via Linear Sketching
We provide efficient algorithms for overconstrained linear regression pr...
read it

Universal Streaming of Subset Norms
Most known algorithms in the streaming model of computation aim to appro...
read it

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
We study the distinct elements and ℓ_pheavy hitters problems in the sli...
read it

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
We introduce difference estimators for data stream computation, which pr...
read it

Sliding window order statistics in sublinear space
We extend the multipass streaming model to sliding window problems, and...
read it

Brazilian License Plate Detection Using Histogram of Oriented Gradients and Sliding Windows
Due to the increasingly need for automatic traffic monitoring, vehicle l...
read it
Symmetric Norm Estimation and Regression on Sliding Windows
The sliding window model generalizes the standard streaming model and often performs better in applications where recent data is more important or more accurate than data that arrived prior to a certain time. We study the problem of approximating symmetric norms (a norm on ℝ^n that is invariant under signflips and coordinatewise permutations) in the sliding window model, where only the W most recent updates define the underlying frequency vector. Whereas standard norm estimation algorithms for sliding windows rely on the smooth histogram framework of Braverman and Ostrovsky (FOCS 2007), analyzing the smoothness of general symmetric norms seems to be a challenging obstacle. Instead, we observe that the symmetric norm streaming algorithm of Braverman et. al. (STOC 2017) can be reduced to identifying and approximating the frequency of heavyhitters in a number of substreams. We introduce a heavyhitter algorithm that gives a (1+ϵ)approximation to each of the reported frequencies in the sliding window model, thus obtaining the first algorithm for general symmetric norm estimation in the sliding window model. Our algorithm is a universal sketch that simultaneously approximates all symmetric norms in a parametrizable class and also improves upon the smooth histogram framework for estimating L_p norms, for a range of large p. Finally, we consider the problem of overconstrained linear regression problem in the case that loss function that is an Orlicz norm, a symmetric norm that can be interpreted as a scaleinvariant version of Mestimators. We give the first sublinear space algorithms that produce (1+ϵ)approximate solutions to the linear regression problem for loss functions that are Orlicz norms in both the streaming and sliding window models.
READ FULL TEXT
Comments
There are no comments yet.