User robby mckilliam - MathOverflow

Maximum magnitude subset sum

2012-11-13T00:41:12Z

Let $z_1,z_2,\dots,z_N$ be vectors from $\mathbb Z^m$ for some $m$. The problem is:

Given a positive integer $p$, find the subset $A_p \subset \{ 1,2,\dots,N \}$ of size $|A_p| = p$ such that $$ \|\sum_{i \in A_p} z_i \| $$ is maximized, where $\|\cdot\|$ is the Euclidean norm.

I am most interested in cases where $m$ is small, not much more than $2$, and $N$ is large, potentially $1000$s.

I would be surprised if this problem had not previously been studied. Has anybody seen it before? Does it have a name?

Hyperplane arrangements and covering numbers

2012-06-10T08:56:24Z

Let $H$ be a set of $(d-1)$-dimensional hyperplanes in $\mathbb{R}^d$. For each hyperplane $h \in H$ let $D(h)$ and $\bar{D}(h)$ be the corresponding half spaces of $\mathbb{R}^d$. For a point $x \in \mathbb{R}^d$, define the function $$ b(h,x) = \begin{cases} 1 & x \in D(h) \\ 0 & \text{otherwise}. \end{cases} $$ For points $x,y \in \mathbb{R}^d$, define the psuedometric, $$ \sigma(x,y) = \sum_{h \in H} |b(h,x) - b(h,y)|. $$ So $\sigma(x,y)$ counts the number of hyperplanes in $H$ that pass between the points $x$ and $y$. I believe that the following lemma is true, but have not yet found a proof.

Lemma

Let $N$ be the number of hyperplanes in $H$. There exists a polynomial $p$ (depending perhaps on $d$, but not on $N$) such that, for every positive integer $k$, there is a discrete subset $T(k) \subset \mathbb{R}^d$ containing not more than $p(k)$ elements with the property that for every $x$ in $\mathbb{R}^d$ there is a point $y \in T(k)$ with $\sigma(x,y) < \frac{N}{k}.$

Another way to state the Lemma is: We require at most $p(k)$ `balls' of radius $\frac{N}{k}$ (with respect to the metric $\sigma$) to cover $\mathbb{R}^d$.

The Lemma is related to what is called Vapnik–Chervonenkis dimension, and it arises when trying to prove results about certain empirical processes. I suspect this result (or something equivalent) to be in the literature, but I have not yet been able to dig it out.

Has anybody seen this result (or something equivalent) before? Alternatively, does anybody know a nice proof?

Answer by Robby McKilliam for Point-wise error estimate in polynomial regression

2011-08-13T00:11:04Z

This is just weighted least squares and here is how I would approach it. To keep my notation simple I'll just have polynomials of order 1. It's trivial to extend the approach to polynomials of any order. Let $a_x$, $b_x$ and $a_y$, $b_y$ be the 'true' coefficients describing the path. So the path is $$ (x(t), y(t)) = ( a_x + b_x t, a_y + b_y t). $$ For convenience I'll pack the coefficients into a column vector $$p_0 = \left[\begin{array}{cccc} a_x & b_x & a_y & b_y \end{array}\right]^\prime $$ where $'$ denotes transpose.

The path is observed at a number of points in time, $t_1, \dots,t_n$ say, and these observations as subject to noise with known covariance matrices $P_1,\dots,P_n$. That is, the observations are pairs $$(x_i, y_i) = (x(t_i), y(t_i)) + W_i$$ where $W_1,\dots,W_n$ are bivariate random variables $W_i = (X_i, Y_i)$ with individual covariances given by the $2\times 2$ matrices $P_1, \dots, P_n$. I'll assume that the $W_1, \dots, W_n$ are independent.

We can write the observations in vector form as $$f = T p_0 + w$$ where $$ f = \left[ \begin{array}{c} x_1 \newline y_1 \newline x_2 \newline y_2 \newline \vdots \newline x_n \newline y_n \end{array}\right]^\prime \qquad T = \left[ \begin{array}{cccc} 1 & t_1 & 0 & 0 \newline 0 & 0 & 1 & t_1 \newline 1 & t_2 & 0 & 0 \newline 0 & 0 & 1 & t_2 \newline \vdots & \vdots & \vdots & \vdots \newline 1 & t_n & 0 & 0 \newline 0 & 0 & 1 & t_n \end{array} \right] \qquad w = \left[ \begin{array}{c} X_1 \newline Y_1 \newline X_2 \newline Y_2 \newline \vdots \newline X_n \newline Y_n \end{array}\right]^\prime.$$ Let $P$ be the $2n\times 2n$ covariance of $w$. So $P$ is block diagonal with diagonals given by the $2\times 2$ matrices $P_1,\dots,P_n$.

You take a weighted least squares approach to estimation, that is, your estimators are given by the minimisers of the quadratic form $$(f - Tp)^\prime P^{-1} (f - Tp). $$ The minimiser is given by $$ \begin{array}{ll} \hat{p} &= (T^\prime D T)^{-1} T^\prime D f \newline &= M (Tp_0 + w) \newline &= p_0 + Mw \newline \end{array}$$ where $D = P^{-1}$ and $M = (T^\prime D T)^{-1} T^\prime D$. So the error in your coefficients is given by $\hat{p} - p_0 = Mw$ and the covariance of the error is $$ C = \operatorname{cov}(Mw) = M \operatorname{cov}(w) M^\prime = (T^\prime D T)^{-1}. $$

You want to know the covariance of the error at time $t$, that is you want the covariance of $$\left[\begin{array}{c} \hat{a}_x + \hat{b}_x t \newline \hat{a}_y + \hat{b}_y t \end{array}\right] - \left[\begin{array}{c} a_x + b_x t \newline a_y + b_y t \end{array}\right] \qquad \text{where} \qquad \hat{p} = \left[\begin{array}{cccc} \hat{a}_x & \hat{b}_x & \hat{a}_y & \hat{b}_y \end{array}\right]^\prime. $$ This is given by the covariance of $$ \left[\begin{array}{cccc} 1 & t & 0 & 0 \newline 0 & 0 & 1 & t \end{array}\right] (\hat{p} - p_0) = K(t)(\hat{p} - p_0) = K M w $$ say. This is $K(t) (T^\prime D T)^{-1} K(t)^\prime$.

More multinomial type integrals over the hypercube

2011-07-28T09:11:06Z

The question is related to my previous question about integrating the multinomial over the hypercube and the motivation for this question is the same, but the integral is a bit different. Here it is,

$$\int_{b}^{a}\cdots\int_{b}^{a} \left( \sum_{i=1}^{n}x_i^2\right)^k \left( \sum_{i=1}^{n}x_i\right)^m dx_1d x_2\dots dx_n.$$

Richard Stanley defltly solved the last integral, but this one does not appear to accept the same approach (the $x_i^2$ gets in the way).

I think I might be able to solve it using the partition function, but the solution is going to be terribly ugly. I am hoping that someone knows a tidy solution, or knows good references for solving integrals of this type.

Answer by Robby McKilliam for Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II

2010-05-25T22:25:54Z

I don't have the answer but I figured I would give you the results of a few quick experiments. Here is what things look like when $n = 5$

and when $n = 10$

and when $n = 50$

and when $n = 1000$

The colour represents the probability, red being large, blue being small. The actual colours are assigned according to the log of the probability. To generate these I used the following matlab

M = [ 0  1/5  0;
     1/5 1/5 1/5;
      0  1/5  0 ];
B = [1];
n = 50;
for i = 1:n
    B = conv2(B,M);
end
colormap(jet(256));
imagesc([-n, n], [-n, n], log(B));

Provided that the `shape' close to the origin becomes sufficiently circular, then the answer to your question is positive.

Answer by Robby McKilliam for How to find a closest integer point to intersection of two lines?

2010-04-29T07:24:50Z

If the point $(x,y)$ is in an obtuse quadrant between the lines the problem is easily solved by enumerating the lattice points in a closed sphere of radius $\sqrt{2}$ about the intersection point so I will only consider the case that $(x,y)$ lies in a acute quadrant.

The problem can be converted to one that is very similar to inhomogeneous Diophantine approximation. I know of at least one algorithm that will definitely find the correct answer in $O\left(\tfrac{1}{\theta}\right)$ operations where $2\theta$ is the acute angle between the lines. The algorithm is a minor modification of that given on page 19 of Vaughan Clarkson's thesis. I am very confident that Cassels' algorithm (or a minor modification of it) will solve the problem in $O\left(1 + \log\tfrac{1}{\theta}\right)$ operations (page 34 of 1), but I am not quite sure how to show it, or what modification needs to be made. Before I describe this, you need to know a little bit about inhomogeneous Diophantine approximation.

Let $\alpha$ and $\beta$ be real numbers. Define the function

$F(p,q) = |\alpha p - q - \beta|$.

The problem of inhomogeneous Diophantine approximation involves minimising $F(p,q)$ over integers $p$ and $q$ where $q$ is positive. The pair $(p, q)$ is called a best approximation if $F(p,q) < F(p',q')$ for all $q' < q$. The best approximations describe the minima found as $q$ and the magnitude of $p$ increase. There are various algorithms than can enumerate all of the best approximations. Two examples are the 'naive algorithm' (page 19 of 1) and Cassel's algorithm (page 34 of 1). The OP's problem is not exactly the same as this, but it is so similar that the algorithms (at least the naive algorithm) carry over.

Let our two lines be $\ell_1$ and $\ell_2$ and let $2\theta < \pi/2$ be the angle between them. It will be easier to describe the approach if we set the intersection of these lines to be at the origin and we look for the nearest point in the translated lattice $\mathbb{Z}^2 + t$ where $t$ is the appropriate translation. Define $\ell$ to be the unique line that passes through the origin and bisects the acute angle between $\ell_1$ and $\ell_2$. The angle between $\ell$ and $\ell_1$ and $\ell$ and $\ell_2$ is $\theta$. The problem can now be stated as:

Find the point $x \in \mathbb{Z}^2 + t$ that is nearest to the origin such that the angle between $x$ and $\ell$ is less than or equal to $\theta$

Let $A(x)$ denote the angle between $\ell$ and $x$. Our motivation is now very similar to that in Diophantine approximation. That is, find all of the best approximations for $A(x)$, our problem is solved by the best approximation that first yields $A(x) \leq \theta$. It so happens that $A(x)$ is a very similar function to $F(p,q)$. To give this some context I will say that $F(p,q)$ is, in a sense, computing an inner product between two vectors, whereas $A(x)$ is computing an angle. In this context it is not surprising that the algorithms for Diophantine approximation can be used.

I will only consider the 'naive algorithm' and I'll just give some geometric insight as to its functionality, this should be enough to convince most people. Working through this rigorously is really beyond a typed answer on MO, but all the required machinery is in 1. The 'naive algorithm' enumerates every point in $\mathbb{Z}^2 + t$ that is a nearest lattice point to any point in the line $\ell$. In other words it consecutively locates (starting from the origin) every lattice point in $\mathbb{Z}^2 + t$ whose Voronoi cell (in this case squares) intersect $\ell$. A picture might be useful

It is not difficult to devise an algorithm which does this, just start at the origin and check where $\ell$ next crosses a boundary of a Voronoi cell. It is also easy to see that the points it locates are a super set of the best approximations for $A(x)$. The first point that the algorithm finds such that $A(x) < \theta$ is the solution to the problem (the blue circle).

This algorithm is called 'naive' because it checks a lot of lattice points that are not best approximations. Cassels' algorithm improves this substantially for the function $F(p,q)$. It's likely that a similar improvement is possible for $A(x)$ and someone might wish to work it out.

The OP (particularly on stack overflow, but also here) seems to have thrown quite a number of red herrings into the problem statement (rather annoying). For example, knowledge of the point (x,y) does nothing other than tell you which quadrant you are looking in. The statement about it converting the problem to NP-complete rather than NP-hard doesn't make any sense. Also, the fact that the lines pass through integer points appears to be irrelevant.

Answer by Robby McKilliam for Estimating direction from a distribution on a circle

2010-10-14T22:59:11Z

I see now that Andrei would like to know what to do when the distribution has 2 modes and is symmetric about these modes. It seems better to just give a second (more detailed) answer rather than complicate the simple answer I gave above (basically I think the idea in gowers comment above is sound, but it's a bit tricky to actually implement).

So, how do we deal with estimating the 'mean direction' of a distribution that looks something like:

Good questions at this point are ''what is mean direction anyway?'' and specifically for the distribution above ''does a mean direction even exist?''

This has been a question I have been looking at a few months now. I'm wary of blowing my own horn a bit here, but I am going to attach a part of my thesis which I think gives satisfactory answers to these questions (I would love to give you the whole thesis, but it's not quite ready for the public to see). I suggest that there are (atleast) two different, but equally reasonable and intutive definitions of mean direction. I argue that the distribution above has no mean in a rigorously definable sense for both of these definitions.

Given $N$ data points $\Theta_1,\dots, \Theta_N$ on a circle there exist very accurate and efficient O(N)-time algorithms to estimate both of these means if they exist. Neither algorithm will converge if used on circular data drawn from the bimodal distribution above as (according to my definition) the means do not exist.

Still, given $N$ data points $\Theta_1,\dots, \Theta_N$ drawn from the bimodal distribution above, if what you want to do estimate one of the ''modes'' rather than the mean direction, then my gut tells me that there probably are efficient and accurate algorithms to do this, although I don't know if they exist in the literature. You could try Fishers book The Statistical Analysis of Circular Data.

Answer by Robby McKilliam for Estimating direction from a distribution on a circle

2010-10-15T23:15:02Z

Ok, so now I will describe why Niels's estimator works so well. Take a bimodal and symmetric circular density function $f$ with modes $p$ and $-p$ (we will assume that $p$ is positive) such as the one plotted in my previous answer. Let $\Theta_1, \Theta_2, \dots, \Theta_N$ be $N$ observations drawn from $f$.

Niels's estimator first computes the complex numbers $e^{i 2 \Theta_n}$ and takes their average $$ \bar{C} = \sum_{n=1}^{N} e^{i 2 \Theta_n} .$$ The estimate, denoted $\hat{p}$, is given by taking the complex argument of $\bar{C}$ and dividing by 2, that is $$ \hat{p} = \frac{\angle{\bar{C}}}{2}$$ where $\angle{\bar{C}} \in [0,2\pi)$ denotes the complex argument. The next theorem describes the asymptotic properties of this estimator. I use the notation $\langle x \rangle_{\pi}$ do denote $x$ taken to its representative inside $[-\pi, \pi)$. So, for example, $\langle 2\pi \rangle_{\pi} = 0$ and $\langle \pi + 0.1 \rangle_{\pi} = -\pi + 0.1$.

Theorem: Let $\lambda$ denote the difference $\lambda = \tfrac{1}{2}\langle 2\hat{p} - 2p \rangle_{\pi}.$ Then $\lambda$ converges almost surely to zero as $N \rightarrow \infty$ and the distribution of the normalised difference $\sqrt{N}\lambda$ converges to the zero mean normal with variance $$ \frac{\sigma_s^2}{c} $$ where $$ \sigma_s^2 = \int_{-\pi/2}^{\pi/2}\sin^2(\theta) f(\langle \theta + p \rangle_\pi) d\theta \qquad \text{and} \qquad c = \int_{-\pi/2}^{\pi/2}\cos(\theta) f(\langle \theta + p \rangle_\pi) d\theta. $$

The definition of the difference $\lambda$ might seem a little strange at first, but it is actually very natural. To see why note that $p$ and the estimate $\hat{p}$ are both in $[0,\pi)$ but, for example, if $p = 0$ and $\hat{p} = \pi - 0.01$ then the difference between these is not $\pi - 0.01$, because the two modes are actually very close to aligned in this case. The correct difference is $\lambda = \tfrac{1}{2}\langle 2(\pi-0.01) - 2 \times 0 \rangle_{\pi} = 0.01$.

The proof of this theorem follows from a very similar argument to Theorem 6.1 (page 87) from my thesis. The original argument is due to Barry Quinn. Rather than restate the proof I'll just give you some convincing numerical evidence.

I've run some simulations for the case when the noise is a sum of two weighted von Mises circular distributions with concentration parameter $\kappa$. So, when $\kappa$ is large the distribution is concetrated and looks something like the picture on the left below ($\kappa = 20$ in this case) and when $\kappa$ is small the distribution is quite spread out and looks something like the picture on the right below ($\kappa = 0.5$). We obviously expect the estimator to perform better when the distribution is quite concentrated ($\kappa$ is large).

Here are the results. The plot below show the simulated variance of $\lambda$ after 5000 trials (the dots) versus the variance predicted in the theorem above for a range of values of $\kappa$ and number of observations $N$. You can see that the theorem does a very good job of accurately predicting the perfomance if $\kappa$ isn't too small.

There is still an open question as to whether this is the best estimator (in the sense of maximally reducing the variance of $\lambda$). It would be possible to derive a Cramer-Rao bound for this estimation problem to give an idea of the best possible performance of an unbiased estimator. I suspect that this estimator performs very near the Cramer-Rao bound. So, in that sense it is close to best possible.

Integrating the multinomial over a hypercube

2011-05-09T12:30:32Z

I have come across an integral of the form $$\int_{b}^{a}\cdots\int_{b}^{a} \left( \sum_{i=1}^{n}x_i\right)^mdx_1d x_2\dots dx_n.$$ I have a solution that makes use of the partition function, but I feel there should be a much nicer solution and I'm sure this has been looked at before. Does anybody know a reference?

Motivation: This integral has appeared whilst trying to compute moments of the Voronoi cell of the lattice $A_n$ (see page 462 of Sphere Packings, Lattices and Groups)

A stochastic process that is 1st and 2nd order (strictly) stationary, but not 3rd order stationary

2010-10-14T12:46:31Z

I asked this question on stats.stackexchange.com a little while back but didn't get an answer. It was suggested that I post it here at the time. There appears to be some migratory problems going on over there. Hopefully, this question is seen as appropriate.

Let $X(t)$ be a stochastic process. We say that $X(t)$ is Nth-order stationary if for every set of ''times'' $t_1, t_2, \dots, t_N$ we have that the joint cumulative density functions $$F_{X(t_1),X(t_2),\dots,X(t_N)} = F_{X(t_1 + \tau),X(t_2 + \tau),\dots,X(t_N + \tau)}$$ for all ''time shifts'' $\tau$. This is quite a strong condition, it says that the joint statistics don't change at all as time shifts.

For example, a 1st order stationary process is such that $F_{X(t_1)} = F_{X(t_2)}$ for all $t_1$ and $t_2$. That is, the $X(t)$ are all identically distributed. It is quite easy to see that a 1st order stationary process need not be 2nd order stationary. Simply assign a correlation structure to say $X(t)$, $X(t+1)$, $X(t+2)$ that does not correspond to a (symmetric) Toeplitz matrix. That is, in vector form, the covariance matrix of $[ X(t), X(t+1), X(t+3)]$ could be given as $$\left[\begin{array}{cc} \sigma^2 & a & b \newline a & \sigma^2 & c \newline b & c& \sigma^2 \end{array}\right]$$ for $a,b,c$ distinct. This is now not 2nd order stationary because $E[X(t)X(t+1)] = a$ and, time shifting by 1 we have $E[X(t+1)X(t+2)] = c \neq a$.

In a similar way (presumably) a process that is 1st and 2nd order stationary need not be 3rd order stationary and this leads to my question:

Does somebody have a nice example of a stochastic process that is both 1st and 2nd order stationary, but not 3rd order stationary?

Motivation: Some of the material I have been expected to teach recently has included stochastic processes and I feel this is a gap in my knowledge. Although no student has actually asked this question yet, I think it is natural enough for it to be asked at some point and I would like to have a neat and simple example.

Answer by Robby McKilliam for Estimating direction from a distribution on a circle

2010-10-14T12:59:13Z

The standard way to solve this is to just consider each of your data points as unit vectors, then take the average of those unit vectors. The direction of this averaged vector is the estimated direction.

There is a large literature on this topic which generally goes by the name of directional statistics. The seminal text on is Mardia and Jupp's book Directional Statistics. This field has a huge number of applications in astronomy, biology, meteorology, engineering etc.

Answer by Robby McKilliam for Computing equivalent vector of random variables from covarience matrix

2010-09-04T04:34:25Z

This question is perhaps more suited to stats exhange. Darsh suggested using the Cholesky decomposition, but this only works if the distribution of the random variables you want to generate is Gaussian. Otherwise there are two techniques that I know of, the Iman-Conover method and the methods based on Copulas.

Maximum differences in sorted vectors of naturals

2010-08-13T06:27:35Z

This question is related to one I asked previously. This is probably a little harder. I had a crack at it today, but have become stuck. I suspect the result is buried in the order statistics literature somewhere, and perhaps somebody is familiar with it. That, or Peter might insta-solve again :).

Given a vector $s$ of integers let $d(s)$ be the maximum difference between any two integers in $s$ when sorted in ascending order. That is, if we sort $s$ in ascending order to obtain $v$, then $$d(s) = \max_{i} (v_{i+1} - v_i).$$

For $s$ a vector of length $m$ from $\lbrace 1,2,\dots,n\rbrace^m$ we must have $0 \leq d(s) < n$.

Given $0 \leq k < n$, how may such vectors have $d(s) = k$ ?

Again, I'm more interested in the case where $n$ is much larger than $m$ and if reasonable bounds can be found for $d(s)$, then this would be useful too.

Note: If $N_k$ is the answer for $k$. Then you should have $n^m = \sum_{k=0}^{n-1}N_k$

Minimum differences in vectors of naturals

2010-08-12T13:26:03Z

I have run into this problem (or something similar to it) a few times now and I am wondering if the answer is known.

Given an vector $s$ of integers let $d(s)$ be the minimum difference between any two integers in $s$, that is $$d(s) = \min_{i,j \in s} |i - j|.$$ For $s$ a vector of length $m$ from $\lbrace 1,2,\dots,n\rbrace^m$ we must have $0 \leq d(s) < n$.

Given $0 \leq k < n$, how may such vectors have $d(s) = k$ ?

I'm more interested in the case where $n$ is much larger than $m$.

Note: If $N_k$ is the answer for $k$. Then you should have $n^m = \sum_{k=0}^{n-1}N_k$

Answer by Robby McKilliam for Is pi a good random number generator?

2010-06-03T22:20:01Z

It is known that $\pi$ doesn't equidistribute very well. I'm not sure what this says (if anything) about the `randomness' of its digits, but it might suggest the use of the golden ratio or Euler-Mascheroni constant over $\pi$.

Answer by Robby McKilliam for Are there interesting problems involving arbitrarily long time series of small matrices?

2010-05-26T14:45:50Z

A very significant application in the context of communications engineering is the modelling of multiple-input-multiple-output (MIMO) communications channels.

These channels are typically modeled by complex $n \times m$ matrices where $n$ is the number of receive antennas and $m$ is the number transmit antennas. The $(i,j)$ entry in the matrix describes the channel between the $i$th transmit antenna and the $j$th receive antenna. In most applications $n$ and $m$ are reasonably small, less than 16. Also, in most real world applications the channel (and hence the matrix) changes over time. This gives you your time series of matrices. In some situations the matrix will even be sparse because some transmit antennas might not see some receive antennas.

There is a seriously huge amount of literature on the MIMO channel and a large amount of it deals with the static case, i.e. for the sake of simplicity it is assumed that the channel doesn't change with time. However there are also many papers that deal with the time varying case. For example:

Chen and Su, "MIMO Channel Estimation in Correlated Fading Environments"

I unfortunately am not an expert in MIMO, but I do know some people who are and could ask them for more details if you were interested.

Answer by Robby McKilliam for Beginning a sentence with a mathematical symbol

2010-05-15T21:40:00Z

I personally find that it is occasionally convenient and natural to start sentences with a mathematical symbol, but I have had coauthors who do not like it, and in this case I typically modify the sentence (into what I sometimes feel is more awkward).

Tara has mentioned a nice trick for amending sentences starting with a symbol and this is typically the approach I have taken. Another approach that I find sometimes works is to consider merging the sentences (perhaps with a little restructuring) so that the symbol follows a comma or a conjunction such as `and'.

I probably have an overly relaxed attitude towards the written language, but in my opinion, if it works and it is clear, do it. I can envisage situations where starting a sentence with a symbol makes the text confusing to read. Obviously it should be avoided in this case.

Answer by Robby McKilliam for Calculating the surface area distribution of two-dimensional projections for a polytope

2010-05-15T07:39:45Z

There is a nice paper on a similar topic by Burger, Gritzmann and Klee "Polytope projection and projection polytopes" . They describe an $O(n^2)$ algorithm to compute the minimum surface area projection of an n-dimensional simplex. According to the paper it is NP-hard to find the maximum surface area projection of a n-dimensional simplex.

Computing a set of coset representatives for $\mathbb{Z}^n / \Lambda$

2010-05-12T02:41:13Z

Let $\Lambda$ be an $n$ dimensional sublattice of the integer lattice $\mathbb{Z}^n$. The quotient $\mathbb{Z}^n/\Lambda$ has order $\sqrt{\det{\Lambda}}$.

What is the best/standard way to compute a set of coset representatives for this quotient?

Edit: I initially forgot to take the square root of $\det{\Lambda}$, which is likely the reason for KCronrad's initial comment.

Answer by Robby McKilliam for Which lattices have more than one minimal periodic coloring?

2010-04-27T13:27:58Z

When you say "reduced basis", I assume you mean that two lattice points are connected in your graph if the distance between them is the minimum distance of the lattice (i.e. the shortest distance between any two lattice points).

There is a simple way to generate a $24$ colouring of $E_8$ using the $8$ colouring you have for $A_8$. It so happens that $E_8$ is isomorphic to the union of 3 translations of $A_8$,

$E_8 = A_8 + (A_8 + g) + (A_8 + 2g)$

where $g = \left( \tfrac{8}{3}, -\left(\tfrac{1}{3}\right)^8 \right)$. That is, $g$ is a vector with one $\tfrac{8}{3}$ and eight $-\tfrac{1}{3}$'s. See Martinet, Perfect Lattices in Euclidean Spaces. So you just need 3 independently coloured $A_8$'s. The resultant colouring will be periodic if the colourings for $A_8$ are periodic. It's likely that this is not the best colouring possible for $E_8$.

Answer by Robby McKilliam for What are some examples of colorful language in serious mathematics papers?

2010-04-24T01:32:53Z

This is perhaps more of a silly play on words than colourful, but I still got a laugh out of it. One page 58 of Conway's 'The sensual (quadratic) form' while discussing Kneser's gluing method a sentence begins:

To further illuminate the utility of glue, ...

Answer by Robby McKilliam for How to define a Voronoi reduced basis?

2010-04-18T14:23:59Z

Excellent question. I don't know the answer and perhaps what I am suggesting is obvious. Nevertheless, I think it's on the right track.

Let $B$ be a basis for $\Lambda$ and let $P$ be the corresponding (origin centred) fundamental parallelepiped. That is, $P$ is the region given by $Bu$ where $u \in [-0.5,0.5]^n$. Clearly $2P \cap \Lambda$ contains representatives of $\Lambda/2\Lambda$. However, the elements in $2P \cap \Lambda$ are generally not the minimal length representatives for $\Lambda/2\Lambda$, those are contained in $2\mathcal{V} \cap \Lambda$ where $\mathcal{V}$ is the (closed) Voronoi cell of $\Lambda$.

Let $d$ be the smallest real number such that $\mathcal{V} \subseteq dP$. Clearly $2dP \cap \Lambda$ is a superset of $2\mathcal{V} \cap \Lambda$ and a suitable value of $c$ is therefore $\lfloor d \rfloor$. We can refine this a little by asking for the diagonal matrix $D$ such that $\mathcal{V} \subseteq DP$. Then we have $n$ different $c$'s, specifically $c_i = \lfloor d_i \rfloor$ where $d_i$ are the diagonal elements of $D$.

The problem is now to find the value $d$ (or matrix $D$). That is, how much do we need to scale the fundamental parallelepiped so that it completely contains the Voronoi cell? Perhaps if $R$ is suitably reduced, say LLL reduced or Korkine–Zolotareff reduced, then bounds on $d$ can be found?

Comment by Robby McKilliam

2012-11-13T05:05:45Z

@Gerry My bad, I obviously mean positive integer! Fixed.

Comment by Robby McKilliam

2012-11-13T03:53:17Z

@Ricky Thanks, I've made that change.

Comment by Robby McKilliam

2012-06-13T00:22:11Z

+1 Couldn't agree more. Sometimes, I think it is a miracle that anything works at all. If I had a dollar for everytime I read, ''Assume that the noise is additive white and Gaussian'', I would be a rich man.

Comment by Robby McKilliam

2012-06-11T23:12:26Z

Sounds like you want a 'maximal inequality'. Not exactly sure how to do what you are asking by I would start at Section 3 of stat.yale.edu/~pollard/Papers/….

Comment by Robby McKilliam

2012-06-11T00:28:30Z

Thanks! I also found Bernard Chazelle's `The discrepency method' to have the same proof on page 206.

Comment by Robby McKilliam

2012-06-10T23:26:17Z

Yes, the hyperplanes are affine.

Comment by Robby McKilliam

2011-10-29T00:32:51Z

I would guess that the answer is `not really'. As far as I know there is not a even a universally accepted definition of the 'normal distribution' on a Remanian Manifold. Probably the closest thing to the normal are those distributions that arise from generalisations of Brownian motion on manifolds. math.northwestern.edu/~ehsu/…

Comment by Robby McKilliam

2011-09-19T12:26:14Z

You might have better luck with this at stats.stackexchange.com

Comment by Robby McKilliam

2011-08-15T18:11:05Z

Sorry, silly typo. Should work just fine for any set of basis functions.

Comment by Robby McKilliam

2011-07-28T11:36:18Z

As I said the $x_i^2$ gets in the way. If is was just two multinomials, one to power $k$, the other to power $m$, there would be no problem, you would get $\exp(tx + sx)$ and everything would work out nicely as before. Perhaps I have missed something though. How do you intend to use the integral of $\exp(tx^2 + sx)$ (which has no closed form solution as far as I am aware) taken to the power of $n$ to efficiently compute the answer?

Comment by Robby McKilliam

2011-07-24T01:25:12Z

How about you just apply Hofstadter's Law: "It always takes longer than you expect, even when you take into account Hofstadter's Law."

Comment by Robby McKilliam

2010-12-12T22:04:33Z

Do you mean to take absolute values? As in $|\mu (f(x)) - f(\mu (x))| > |m (f(x)) - f(m (x))|$?

Comment by Robby McKilliam

2010-12-06T21:17:06Z

I like the updated part of this question +1. I recommend deleting the first part (However, don't do this if you have some specific reason not too). If you don't mind me asking, in what application does this problem occur? Also, what justifies your use of the von Mises Fisher distribution here?

Comment by Robby McKilliam

2010-12-01T21:06:57Z

There is a big literature on this. Typing 'circle fitting' into google with give you a lot of resources. Most of the approaches I know of deal with estimating both the center and the radius, but they could easily be adapted to estimate just the center if that is what you want. Your question is probably more appropriate for CrossValidated stats.stackexchange.com/questions. You might have better luck there.

Comment by Robby McKilliam

2010-10-16T02:51:33Z

Oh yes! I much prefer Herman Wouk's ryhming version ''When in danger or in doubt, run in circles, scream and shout'' anyway. Thanks!