Questions tagged [sampling]
The sampling tag has no usage guidance.
78
questions
2
votes
0
answers
40
views
When can convolutional integral operators be sampled
Consider an integral operator $F:C^{1/2}([0,T],\mathbb{R}^n)\rightarrow \mathbb{R}$ of the form
$$
f\mapsto \int_0^T f(t)^{\top}\kappa(T-t)dt,
$$
for some $\kappa\in C^{\infty}(\mathbb{R})(\mathbb{R},\...
3
votes
1
answer
310
views
Importance resampling with exponential weighting
Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...
2
votes
2
answers
205
views
Is there something like a "self-avoiding Markov chain" on a continuous space?
If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.
However, as far as I can see they are ...
1
vote
0
answers
34
views
Does the constrained Wasserstein barycenter admit a blue noise property?
Let $(E,d)$ be a metric space and $\nu$ be a probability measure on $\mathcal B(E)$. In this paper, it is mentioned that sampling from $\mu$ can be described as choosing $n\in\mathbb N$, $x_1,\ldots,...
0
votes
0
answers
21
views
Minimizing $\|Ax\|_2^2$ over the simplex for a very fat matrix
Suppose I have a really fat $mxN$ matrix (with $N>>m$). I want to find an $x$ in the simplex (i.e $x’1=1$ and $x_i\geq 0$) that minimizes $\|Ax\|_2^2$.
The only operations I can practically do ...
7
votes
1
answer
212
views
Square-root lattices: where do they appear?
As an experimental physicist working on crystallography I'm often dealing with the reconstruction of an object from intensity data that emerge from an imaging device. In mathematics the problem is ...
0
votes
0
answers
57
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
37
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 ...
2
votes
1
answer
133
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
173
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
250
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
463
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
31
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
127
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
244
views
Injectivity of the convolution operator $f \mapsto (k*f(s))_{s \in S}$ via sampling at $S=\alpha \mathbb Z$
Let $S \subset \mathbb R$ be a set of sampling points, say $S = \alpha \mathbb Z, \alpha >0$.
Let $k$ be some convolution kernel and $A$ the operator which maps some $f$ to the sequence
$$
Af = (k*...
5
votes
0
answers
117
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_{...
1
vote
1
answer
55
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
204
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 \...
2
votes
1
answer
66
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}...
3
votes
1
answer
133
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
65
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
546
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
133
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
257
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 ...
2
votes
1
answer
616
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
32
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
47
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: ...
4
votes
2
answers
682
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
125
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
213
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
107
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 ...
1
vote
2
answers
297
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
89
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
375
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
366
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
643
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
68
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
120
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
251
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
142
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
630
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
44
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
215
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
200
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
144
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
804
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
61
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 $...