Questions tagged [sampling]
The sampling tag has no usage guidance.
74
questions
0
votes
0
answers
28
views
Alternative to the Sampling Theorem / Invertible transform with sampling criteria
I seek a transform $T$ that operates on real-valued $x(t)$, that
Is perfectly invertible
Has discrete counterpart with continuous reconstructor
Provides conditional reconstruction guarantees
...
3
votes
0
answers
33
views
Invertibility of the sampling matrix
Given a function $f: \mathbb{R}^2\rightarrow\mathbb{C}$ sampled as a matrix $F_{ij}$ on some ractangle $[a,b]\times[c,d]\subset\mathbb{R}^2$ with steps $\Delta x$ and $\Delta y$ as the stepsizes so ...
1
vote
1
answer
77
views
Given iid samples from the joint distribution $P$ of pair of r.v.'s $(X,Y)$, how to get iid samples from independence coupling $P_X \otimes P_Y$?
Let $(X,Y)$ be a pair of random variables on a measure space $\mathcal T \subseteq \text{"subsets of }\mathbb R^2\text{"}$, with joint probability distribution $P$.
We don't assume $X$ and $Y$ are ...
4
votes
1
answer
167
views
Integral of $\ln(1/|f|)$ for $f$ bandlimited
I came across the following assertion: if $f\in PW_\infty([-a,a])$, i.e. the Bernstein space of functions in $L^\infty(\mathbb{R})$ which are the Fourier transform of a distribution supported on $[-a,...
2
votes
1
answer
130
views
Shift-invariant spaces
We can define a shift-invariant space as
$$V_{\varphi}(\mathbb{Z}):=\left\{\sum_{k\in\mathbb{Z}}c_k\varphi(\cdot-k):(c_k)\in \ell_2\right\},$$
where convergence of the series is taken to be in $L^2(\...
5
votes
3
answers
187
views
Probability of an edge in a random graph
Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...
1
vote
0
answers
27
views
Correlating two matrices $A,B$ with stochastic dependency structure imposed by cross-validation
Consider a labelled data set
$$D = \{(x_1, y_1),...,(x_n, y_n)\} $$
on which we want to evaluate a machine learning algorithm using $k$-fold cross validation with $m$ different random seeds. This ...
1
vote
1
answer
118
views
Intuition of the "work" done by random variables in Monte Carlo methods (incl. MCL)
(I've tried Math SE, but have so far come up empty handed, so I'm trying my luck here.)
I would like to get a better intuitive understanding of why Monte Carlo works so well in approximating a ...
3
votes
0
answers
172
views
Injectivity of the covolution operator $f \mapsto (k*f(s))_{s \in S}$ via sampling at $S=\alpha \mathbb Z$
Let $S \subset \mathbb R$ be a uniform grid, say $S = \alpha \mathbb Z, \alpha >0$.
Let $k$ be a square integrable function and $A$ the operator which maps $f \in L^2(\mathbb R)$ to the sequence
$$
...
5
votes
0
answers
108
views
Which operations commute with fractional translation?
Let $\mathbf{v}$ be a real signal (i.e., an infinitely long vector).
A translation operation $T_{s}\mathbf{v}$ with integer $s$ is trivially
defined by $\forall i,s:\left(T_{s}\mathbf{v}\right)_{i}=v_{...
0
votes
0
answers
28
views
Sampling after sorting vs sorting without sampling
Given a probability distribution $(p_1,\cdots,p_d)$ and integer $k$.
We can sample the distribution $k$ times. For any obtained sample $(X_1,\cdots,X_d)$ with $X_i$ denoting the occurrence of $i$, we ...
0
votes
0
answers
14
views
Subset estimation from positive and negative samples
I am looking for the name of the following (family of) problems:
given a known set $K$ and an unknown subset $G \subset K$, and the values of the characteristic function $\mathbb 1_{G}(x_i)$ for some ...
1
vote
1
answer
54
views
Distribution of a two-part sampling process
I have a known distribution $f(x)$ (in fact, I can safely assume that $f(x)$ is the Maxwell-Boltzmann distribution, i.e. $f(x)\propto x^2 \exp(-x^2)$). I take $N$ samples from the distribution, but am ...
0
votes
1
answer
134
views
Random sampling from modified Erlang distribution [closed]
I am tasked with randomly sampling from the following probability density function, which is a modified Erlang Function:
$$f(k,q,\nu)=\frac{(k q)^{k-1}}{[(k-1) !]^{v}} \quad \text { with } \quad q \...
1
vote
1
answer
59
views
Column subset selection with least angle optimization
Given a matrix $A$ I need to select a "representative" subset of its columns so that the each non-selected column is as close as possible to a selected one.
Formally:
Given $A \in \mathbb{R}...
2
votes
1
answer
116
views
Fast sampling of matroids
In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...
2
votes
0
answers
57
views
Are two degree sequences compatible, for random simple graph generation?
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
3
votes
1
answer
315
views
Relation between signal derivative and frequency spectrum
I want to sample a signal whose derivative I know to be bounded by physical constraints. The sampling is disturbed by gaussian noise, hence I need to filter the sample with a lowpass filter.
Since I ...
1
vote
1
answer
119
views
Sampling i.i.d. variables with restrictions
General Problem: Suppose $X_1,\ldots,X_n \sim \mathbb{P}_X^{\otimes n}$ is a finite sequence of i.i.d. (real- or integer-valued) random variables. Suppose $A\subseteq \mathbb{R}^n$ is a set of "...
6
votes
0
answers
235
views
Probability that a random multigraph is simple
Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
1
vote
1
answer
415
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
0
votes
0
answers
31
views
Condition on the point cloud matrix making the points "generic" in the uniform sense
For a matrix $X\in\mathbb{R}^{d\times n}$, what condition can I impose on $X$ to make the collection of its columns generic in the sense that they look like the result of uniformly sampling a convex ...
0
votes
0
answers
43
views
Yates-Grundy draw-by-draw sampling inclusion probabilities
Is there an efficient algorithm to calculate the inclusion probabilities (the probability that an item will be included in a sample) in the Yates-Grundy draw-by-draw sampling?
Sampling description: ...
3
votes
2
answers
503
views
Invariant measure vs Riemannian measure on Stiefel manifold
I'm interested in sampling uniformly from the Stiefel manifold $V(k, n)$, but while researching how to do this I came to wonder the following.
In Edelman et al. [1] there are presented two ...
1
vote
1
answer
121
views
Random optimization problem
Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution ...
5
votes
1
answer
186
views
What is the pdf of Laplace distribution conditioned on a plane? How can I sample from it?
Our goal is to sample from the Laplace distribution conditioned on a linear subspace. Here are the details of this problem.
Let
$$p(x) \propto \exp(-\|x\|_1/\sigma)$$
be the pdf of the Laplace ...
-2
votes
1
answer
45
views
Using common samples to numerically estimate pairwise equality of three random variables
Let $X,Y,Z$ be three discrete random variables which I can numerically sample. I need to numerically estimate the probability that $X=Y$ and the probability that $X=Z$. I would like to know whether ...
2
votes
0
answers
105
views
Can computers take uniform samples from a polytope?
For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...
0
votes
2
answers
261
views
Use Importance sampling for multimodal and multivariate distribution draws, how to choose proposal distribution?
I'm in trouble trying to generate samples following a particular distribution which is not numerically known perfectly. Let us consider a $R^n$ space provided with an orthonormal base $( e_{1},...,e_{...
2
votes
2
answers
87
views
Draw samples from distribitions in the neighborhood of a fixed distribution
Disclaimer
Sorry in advance for vagueness. I'm still trying to get my ideas right on this one.
Setup
So, let $P$ be a distribution on a Euclidean space $X$ with an $\ell_p$ metric, and let $P_\...
8
votes
1
answer
330
views
Expectation inequality for sampling without replacement
Is the following proposition correct?
$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement.
$f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric:...
4
votes
1
answer
352
views
Minimize the variance of a Boltzmann distribution
N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here).
...
1
vote
1
answer
461
views
Uniform sampling of random connected graph with given number of vertices/edges
I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not ...
2
votes
1
answer
66
views
Sampling with non-uniform probabilities
Let $p_1,p_2,...,p_n$ are given probabilities. ($\sum_{i=1}^n p_i =1, p_i \geq 0 $). Is there any distribution, which picks $k\leq n$ distinct elements from $1,2,...,n$ such that $P(i \in S) = k p_i$ ...
1
vote
1
answer
117
views
Plancharel-Pólya inequality for functions of exponential type
If $f(z)$ is an entire function of exponential type $\tau$ and $p$ a positive number such that that $$\int_{-\infty}^{+\infty}|f(x)|^pdx<\infty$$
then it can be proven that $$\int_{-\infty}^{+\...
4
votes
1
answer
248
views
Combinatorial computational problem about 0-1 vectors and sampling algorithms
Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...
1
vote
1
answer
133
views
Sampling set: relatively dense and uniformly discrete
The Paley-Wiener space of a domain $\Omega\subset\mathbb{R}^d$ is the set $$PW_\Omega:=\{f\in L^2(\mathbb{R}^d):\text{supp}\widehat{f}\subset\Omega\}.$$
We say that a discrete set $\Lambda\subset\...
7
votes
1
answer
585
views
Randomly covering a sphere
Let $S$ be the $n$-dimensional unit sphere in the Euclidean space. Further,
let $X_1,\ldots,X_k$ and $Y_1,\ldots,Y_m$ be iid $S$-valued random variables with common (unknown) distribution $\mu$. With $...
4
votes
1
answer
1k
views
How to measure distribution of high-dimensional data
I have to methods of projecting random samples in $\mathbb{R}^n$ onto a manifold defined by $C(q)=0$, which is a lower-dimensional subset. Now, samples in $\mathbb{R}^n$ are uniformly distributed. ...
1
vote
0
answers
42
views
RMHMC sampling in non-parametric setup
The aim is to sample distributions using Fisher information (as mass matrix in Hamiltonian MCMC sampling). Details can be found in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.580&...
0
votes
0
answers
179
views
Expected value of parametrized Gibbs distribution w.r.t another probability distribution
Let $\mu$ be a compactly supported probability measure on a finite-dimensional euclidean space (for simplicity) $\mathbb E$, and suppose $\mu$ has density. For a random point $x \sim \mu$,
consider ...
1
vote
1
answer
189
views
How to sample a path between 2 states in a Markov chain
Given an ergodic Markov chain and 2 states $x$ and $y$, how may one algorithmically sample a path (of finite length) $x =: s_0 \rightarrow s_1 \rightarrow \ldots \rightarrow s_T = y$ between $x$ and $...
1
vote
1
answer
103
views
Bounding function by random sampling
Let $f(x): \mathbf{C} \to \mathbf{C}$ be a complex valued polynomial of degree $n$, and suppose that for a random point $z$ sampled uniformly from the unit disk $|z|\leq 1$ we have
$$\mathbf{P}_{z}( |...
0
votes
1
answer
139
views
Efficiently Sampling of Multivariate Distributions in the Vicinity of a Manifold
I am given a multivariate distribution, that maps each point of $\mathbb{R}^n$ to its probability of being drawn as sample and, the convolution $\mathcal{S_r}\times\mathcal{M}$ of a manifold $\mathcal{...
3
votes
1
answer
770
views
Sampling from a particular multivariate probability distribution
Given $3$ real variables $x_1, x_2, x_3 \equiv \bf{x}$, consider their probability density function (PDF)
\begin{equation}
P({\bf x}) = C \, p(x_1) \cdots p(x_3) \exp[f({\bf x})],
\end{equation}
where ...
1
vote
0
answers
59
views
2-step sampling from a conditional density
The setting is as follows:
We are given two random variables $X : \Omega \to \mathbb{R}$ and $\Theta : \Omega \to T$ for some 'parameter space' $T \subset \mathbb{R}$, and
1) we know the density of $...
3
votes
2
answers
225
views
Sampling Theorem for non-bandlimited Functions
The classical Shannon sampling theorem states that
a bandlimited function with $\mbox{supp } \hat f\subset [-1/2,1/2]$ can be uniquely determined by its samples $(f(i))_{i\in \mathbb{Z}}$ (The symbol $...
1
vote
0
answers
62
views
Simulate a graph from a certain distribution
I am wondering if anyone can indicate whether the following is a solved problem. I don't care about time of the algorithm currently.
Consider a general probability distribution F on simple graphs ...
6
votes
1
answer
185
views
Sample integer points of cross-polytope uniformly
For $r,d\in\mathbb{N}$, let
$$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$
be the set of integer points of the $d$-dimensional cross-polytope with radius $r$.
What is (...
0
votes
0
answers
48
views
Efficient sampling from a polytope with large number of contraints [duplicate]
As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...