Questions tagged [sampling]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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},\...
Annie's user avatar
  • 71
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_{...
Minkov's user avatar
  • 1,107
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 ...
0xbadf00d's user avatar
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,...
0xbadf00d's user avatar
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 ...
AspiringMat's user avatar
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 ...
user avatar
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 ...
OverLordGoldDragon's user avatar
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 ...
sqrt6's user avatar
  • 61
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 ...
dohmatob's user avatar
  • 6,338
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,...
pipenauss's user avatar
  • 297
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(\...
AKG's user avatar
  • 49
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. ...
Matthieu Latapy's user avatar
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 ...
Joker123's user avatar
  • 153
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 ...
litmus's user avatar
  • 91
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*...
J. Swail's user avatar
  • 349
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_{...
Daniel Soudry's user avatar
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 ...
Kunstmord's user avatar
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 \...
Jack Rolph's user avatar
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}...
Felix Goldberg's user avatar
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 ...
Tobias Windisch's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
LucioPhys's user avatar
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 "...
Peter Wildemann's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
Davide Papapicco's user avatar
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 ...
Min Wu's user avatar
  • 443
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: ...
Josef Ondrej's user avatar
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 ...
Călin's user avatar
  • 261
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 ...
Penelope Benenati's user avatar
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 ...
BOYI's user avatar
  • 53
-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 ...
Adrian Radillo's user avatar
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 ...
Daron's user avatar
  • 1,721
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_{...
Gavroche's user avatar
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_\...
dohmatob's user avatar
  • 6,338
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:...
Rui Zhang's user avatar
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). ...
dohmatob's user avatar
  • 6,338
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 ...
Szabolcs Horvát's user avatar
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$ ...
Ethan's user avatar
  • 145
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}^{+\...
pipenauss's user avatar
  • 297
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 ...
Penelope Benenati's user avatar
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\...
pipenauss's user avatar
  • 297
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 $...
Christopher's user avatar
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. ...
Jeremy Span's user avatar
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&...
Madhuresh's user avatar
  • 157
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 ...
dohmatob's user avatar
  • 6,338
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 $...
dohmatob's user avatar
  • 6,338
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}( |...
Lior Eldar's user avatar
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{...
Manfred Weis's user avatar
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 ...
James's user avatar
  • 323
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 $...
Fabian Werner's user avatar