Questions tagged [compression]
Data compression is a process used to reduce the number of bits used to store a "message". Compression can be lossless or lossy. Lossy compression is an option for audio and visual data, whereas many other applications require lossless compression.
50
questions
0
votes
0
answers
19
views
Is there a natural extension of the ACF/PACF to more general measures of dependency?
Assume that we have a time series that we want to model as a stationary real-valued stochastic process: $$X_t , t \in \{0, 1, \dots \}.$$
Two complementary measures of linear dependence between the ...
- 327
0
votes
0
answers
27
views
Optimal variable-time sampling of a real-time data stream
Here's a signal processing/information theory problem that I've encountered in a software engineering context:
Say I have a logging utility in my application that I use for recording timestamped ...
- 644
1
vote
0
answers
96
views
Linear Distance in Latent Feature Space of an AutoEncoder
I would like to perform a cluster analysis on a mixed data set containing continuous, categorical and binary data.
As I have 93 features in total, I thought it might help to use an AutoEncoder to
...
- 11
0
votes
0
answers
35
views
Is there a Hidden Markov Model compression scheme for time series?
Hidden Markov Models (HMMs) are very useful for time series analysis and inference. At the same time, probability distributions over a data type are used in finding compression schemes for data of ...
- 210
0
votes
1
answer
114
views
Reverse engineering device RGB data
I'm working with a device that maps certain RGB colors to a 7 bit value (0-127):
I want to reverse the process, i.e. given any RGB triplet, what is the (closest) corresponding color index (0-127)? ...
- 111
0
votes
1
answer
48
views
Rotation-sensitivity of SVD
Suppose I perform a truncated SVD on a symmetric, PSD matrix $A \in R^{N \times d}$ (lowering the dimensionality from $d$ to $k$). Further suppose that there is a rotation matrix $Q$ such that some of ...
- 239
1
vote
0
answers
23
views
Evaluate two lossy compression algorithms
I am trying to evaluate several methods to compress some 2D data points.
The algorithm itself is not relevant, but from the output, I can compute the MSE and the number of points (which can be used to ...
- 131
2
votes
0
answers
309
views
Understanding Minimum Description Length for Time Series
I am trying to reproduce (in Python) the minimum description length work found near Figure 6 from this paper along with their sample Matlab code.
...
- 504
2
votes
0
answers
96
views
Optimal compressibility and PCA
I have a population $\mathcal{X}$ of $N$ samples extracted from a multivariate gaussian random variable $\mathbf{x} \in \mathbb{R}^d$. Let us define a transformation $f_{d\rightarrow r} (\mathbf{x}) = ...
- 31
1
vote
1
answer
368
views
What is the difference between Karhunen-Loeve transform (KLT) and sparse dictionary learning?
Both are data adaptive (unlike something like DCT), both can sparsely approximate data (KLT by truncation, dictionary learning by L1 sparsity), yet they different pretty significantly in its ...
- 11
0
votes
1
answer
107
views
Is Prediction the same as Compression?
Just came across this transcript that states:
The principle is that prediction is the same thing as compression. And
what that means is that whenever you have a prediction algorithm, you
can also get ...
- 207
1
vote
1
answer
83
views
Image Compression Approaches for CNN
I have a set of images, which are quite large in size and as such do not easily fit into memory for feeding a CNN. (1000x1000). I'd like to compress and encode these images, such that little ...
- 111
0
votes
1
answer
21
views
What criteria charactarize the minimum rate for transferring information without loss?
My question in other words is: what is the condition to do data compression and later decompress the data without any loss ?
- 123
2
votes
0
answers
445
views
Data compression for graph plotting [closed]
I am using Google Charts to plot a large data set. The database contains one record for every two seconds; five minutes' worth of data yields 150 records (data points) and the result is acceeptable. ...
2
votes
0
answers
235
views
Invertibility of Random Fourier Features
Is it possible to approximately reconstruct a point $ \mathbf{x} $ in a vector space (say $\mathbb{R}^n $) given it's randomized feature map $ z(\cdot) $ and respective projection $ z(\mathbf{x})$ (in ...
- 944
3
votes
0
answers
33
views
From a deep learning point of view, is there a lower limit on the number of hours of speech needed to train a neural net
From a deep learning practitioner's point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
- 411
1
vote
0
answers
23
views
Finding a small description length/compression of variable length lists of rational numbers [closed]
Suppose we have data in form of variable length lists of rational numbers where the order in which the numbers are listed is arbitrary. What is the best way to represent/encode this data so that all ...
- 11
3
votes
1
answer
95
views
Is there a formal relation between weight regularization and compression?
In my understanding, compression, strictly speaking, means that we diminish the amount of data required to describe something, such as a model. E.g. compressing an image file means to create a file ...
- 2,789
1
vote
1
answer
2k
views
Minimum Input Dimension for Autoencoder Neural Network
Model: Assume we want to learn patterns using an autoencoder neural network. In the simplest case, such a network is "shallow" with 1 hidden layer, takes a $d$-dimensional numerical input vector $x$, ...
- 697
2
votes
0
answers
333
views
Regarding the quantics tensor train (QTT) format
I originally posted this question in Data Science Stack Exchange, however, I think this forum may be better for this question.
I believe I have a fair understanding of the tensor train (TT) format, ...
- 21
1
vote
2
answers
161
views
Compression of 18000 curves
I have over $18000$ curves that I need to compress to save $\geq 50\%$ of space. Each curve is described by points $f(1), f(2), ..., f(96)$, each $f(x)$ is 8-bit long. The curves in compressed form ...
- 123
2
votes
0
answers
326
views
Is there an extension of PCA for data embedded in hyperbolic spaces?
I'm working on a project where we are embedding data into an n-dimensional Poincare ball similar to this paper. However, we'd like to take the additional step of reducing this data to a 2-dimensional ...
- 21
2
votes
2
answers
88
views
Lossless Compression Of Data Tables Leveraging Exploratory Analysis?
Lossless compression of data tables seems a natural application of automated modeling based on exploratory data analysis methods. While such automatically generated models are not reliable for ...
- 271
0
votes
0
answers
37
views
Differentiable remover of repetition?
In a pet project to see why automatic phonetic transcription is so hard, I would like to use both audio data where each sample is annotated by the sound to which it belongs (a phonetic segments tier) ...
- 181
1
vote
1
answer
744
views
Mutual information of BSC Channel
As we all know, formula for mutual information is as follows:
$ I(X, Y) = H(Y) - H(Y|X) $
In case of Binary Symmetric Channel with flip probability equal to $f$ and both alphabets of size $2$:
$ I(...
2
votes
0
answers
201
views
Iterative PCA in C++
I have a time-series data set (10,000 samples/sensors over ~2,000 time-series samples). I would like to keep the covariance structure in the data (sensor-sensor covariance) up to some error, while ...
- 21
1
vote
2
answers
279
views
Binary Sparse Coding
In this binary sparse coding paper referenced in the Goodfellow/Bengio/Courville deep learning book (https://fias.uni-frankfurt.de/~bornschein/papers/HennigesEtAl_lva2010.pdf), the parameter $\pi=p(...
- 171
2
votes
1
answer
358
views
Combined PCA and Quantization
I did some PCA on a dataset to reduce the size without compromising too much on their actual information.
However, I learnt that quantization is also an effective technique to do this. I guess it is ...
- 115
6
votes
2
answers
2k
views
When and why do we use sparse coding?
Sparse coding is described as "given an input $X$, finding a latent representation $h$ such that h is sparse and the input can be reconstructed as well as possible." (source: https://www.youtube.com/...
- 173
1
vote
2
answers
2k
views
Can white noise be (losslessly) compressed?
Can I expect a vector whose components are i.i.d. Gaussian noise to be compressible (lossless compression)? Why or why not? If so, how much?
EDIT: To be clear, I mean "compressible" as in "...
- 416
28
votes
4
answers
3k
views
Kullback-Leibler divergence WITHOUT information theory
After much trawling of Cross Validated, I still don't feel like I'm any closer to understanding KL divergence outside of the realm of information theory. It's rather odd as somebody with a Math ...
- 2,364
3
votes
3
answers
5k
views
How does SVD save space?
We start with an $m \times n$ matrix before SVD. After SVD, we have three matrices of sizes, $m \times m$, $n \times n$ and $m \times n$. How do we save space then if now we have three matrices ...
- 265
2
votes
0
answers
332
views
Relation between cross-entropy loss on softmax output and bits per base in DNA sequence compression
When training an autoencoder (softmax in outputlayer), for DNA sequence compression (by minimizing a cross-entropy loss function), how can you calculate the number of bits per base required for the ...
- 21
3
votes
1
answer
336
views
Compressed Sensing: Missing Fourier Coefficients?
This question is regarding the problem of reconstructing a signal given only a subset of the Fourier coefficients are observed:
$$\min_x \|x\|_1 \text{ subject to } y = Ax$$
where $x = (x_1,x_2,\...
- 1,322
2
votes
1
answer
115
views
Local redundancy - Product Quantization and global redundancy - Residual Quantization connection
I am currently reading Compressing Deep Convolutional Networks using Vector Quantization paper. The paper states in section 3.2.5 that Product Quantization explores some local redundancy and Residual ...
- 143
5
votes
1
answer
443
views
Why low rank expansions can exploit the redundancy that exist between different feature channels and filters?
I read Jaderberg et al., 2014 paper about Speeding up Convolutional Neural Network with Low Rank Expansions. In the introduction, it is written in bold font:
Our key insight is to exploit the ...
- 143
2
votes
0
answers
303
views
Should we pre-train neural networks on compressed data?
I believe this is actually related to the topic of "auto-encoding" but my question is trying to express some basic gaps in my knowledge that I have not seen directly addressed anywhere.
You can train ...
- 121
2
votes
2
answers
120
views
Detecting if a File is Compressed using Machine Learning?
Let's say that I want a 'general' way using some machine learning model to classify if a file is possibly compressed or not.
I don't need a 100% success rate.
How would you approach this?
I ...
- 21
1
vote
0
answers
99
views
Clustering technique and validation for distance based on file compression
I have a distance matrix based on a normalized compression distance between files:
$$ d(x, y) = \frac{ C(xy) - \min \{ C(x), C(y) \} } {\max \{ C(x), C(y) \}} $$
Here, $C(xy)$ is the concatenation ...
- 113
0
votes
0
answers
16
views
Removing minimally informative bits
Each sample in my data set is an $N$-bit bit-vector (say $N$=200). The bits in each sample are not uncorreleated within the sample.
I built a matrix $S_{N \times N}$ with each $s_{ij}$ being the ...
- 255
2
votes
0
answers
196
views
Analyzing 3D data: What can be done?
I am new to this kind of analysis, and I want to know what values I can look at in 3D data.
The data itself is a 3D volume $(x,y,z)$ with a floating point value in every coordinate.
It is a ...
- 43
10
votes
1
answer
10k
views
Comparison of entropy and distribution of bytes in compressed/encrypted data
I have some question which occupies myself for a while.
The entropy test is often used to identify encrypted data. The entropy reaches its maximum when the bytes of the analyzed data are distributed ...
- 201
2
votes
1
answer
437
views
Distance independent approximation of Nearest Neighbor/k-NN.
Nearest neighbor/k-NN for use with Normalized Compression Distance. I wonder if there exist any approximation of NN/k-NN algorithm which work for all distance measures ? I would like to test ...
- 1,687
1
vote
1
answer
727
views
Dense Data Compression (Delta Encoding?)
Let $X $ be a dense integer set such that its elements are closely knit in value.
For instance:
1 1 1 1 2 2 2 2 2 3 3 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 8 8 ...
I am ...
user12760
4
votes
1
answer
138
views
Weights of random sets of random 32-bit strings
I have random sets of $N$ random 32-bit strings,
where all bits are i.i.d. with $\mathbb{P}(0) = \mathbb{P}(1) = 1/2$.
Define
$\ \ \ \ $weight( 32-bit x ) = number of 1 bits in x, i.e. Hamming ...
- 3,297
3
votes
2
answers
1k
views
How to compress sets of integer series?
I have a set of integer series $S_1$, $S_2$, ... $S_n$. Each series has 3600 data points. Each data point is a positive integer. Each data point is stored as an ...
- 83
4
votes
4
answers
1k
views
Ultimate compression algorithm
I was not sure where to put this question, so I put it here. Feel free to move it to another stack exchange site moderators.
Lets say I have a 10 gigs of pictures (or for that matter any type of data,...
- 143
7
votes
2
answers
280
views
Compression theory, practice, for time series with values in a space of distributions (say of a real random variable)
Example of problem: Part of our research team is working on providing operationally wind power forecast. Usually, since there are different time scalse that interest forecast user, a forecast is ...
- 6,515
2
votes
1
answer
913
views
How to compute theoretical compression limit?
Assume we have a sensor field with dimension M*M. In order to apply any data compression technique, first I want to know what is the compression limit or minimum entropy of the entire sensor field. ...
- 21
0
votes
2
answers
1k
views
Suggest a method for statistical data compression
There's a lot of work done in statistics,
while state-of-art in lossless data compression is apparently this:
http://mattmahoney.net/dc/dce.html#Section_4
Please suggest good methods/models ...
- 103