- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Re: n-D median redefined
by Steve Witham 06 Dec '07

06 Dec '07

I should point out explicitly that Richard's definition minimum of sum of absolute values of differences and mine: zero-crossing-like-point of sum of unit vectors of differences Are like the minimum of a function and the zero of its derivative-- they tend to agree. (Waffling because I'm not equal to the hairiness.) >From: "Fred lunnon" <fred.lunnon(a)gmail.com> > >It's not at all obvious whether this function has multiple (local) minima >--- in which case it may be nontrivial to compute. Almost certainly, >the sum of the squares of the distances would be more tractable. More tractable, yes, but isn't the minimum of the sum of squares the average rather than the median? Maybe you could sum sqrt( distance^2 + c )...but for what c? >What relation might these definitions bear to the convex hull stripping >algorithm mentioned earlier? WFL Besides that, as Gareth McCaughan points out, they're identical in the 1D case, both ignore the distance to the points and pay attention to their direction. I suspect the convex peel has a different purpose: it lets you strip away some fraction of points as "outliers" and consider the remaining points more reliable data. The convex peel can be used as a multi- dimensional version of the quantile (as in "in the top 10%") or as a way to estimate density. >From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> (quoting Richard Harter:) > > > >and find the set of x's such f(x) is a minimum. All of these > > > >are valid medians; however the centroid of the set is in some > > > >sense the most central median. > >The centroid needn't be a median in this sense at all in dimensions >other than 1. Richard is talking about the centroid of the set of median- like points, not the centroid of the original set. >In two dimensions, suppose your points consist of the vertices >of a regular 999-gon inscribed in |z|=1, together with a single >point at (10^6,0). Then the centroid is (1000,0) but f(1000-h,0) >is approximately f(1000,0) - 998h and so the centroid isn't even >a local minimum of f. Sure, this is the whole idea of the difference between an average and a median. >Of course the corresponding property doesn't hold for f even >in two dimensions. In fact, if g from R^2 to R has the >property that sum_A g(x-a) is constant when x is a convex >combination of the elements of A, then I claim g is constant; [...] In any case my/Harter's median functions inside the convex hull aren't constant. >Is there some f of less simple form with some such property >that would let us play the hull-stripping game? I think of hull-stripping as a cheap substitute. It's like you're asking for a better approximation to a calculation error. But... with the sum of the absolute differences, you can draw contours (I should improve my applet). By the way there are also concave peels based on the Delaunay triangulation. The funny thing is, I don't think the convex peel is easier to calculate. J.L. Gastwirth, its inventor, has kindly sent a couple papers, saying, >I am not sure that what you did is exactly what I did but it is related. >Here is my paper and an extension I did in 1985. The issue you discuss >is also related to work of Prof. Regina Liu at Rutgers on defining the >median in terms of Depth in multivariate data. Gastwirth, J.L. (1966), On Robust Procedures. Journal of the American Statistical Association, 61, 929-948 http://tinyurl.com/2xt3qp The Use of Maximin Efficiency Robust Tests in Combining Contingency Tables and Survival Analysis Joseph L. Gastwirth Journal of the American Statistical Association, Vol. 80, No. 390. (Jun., 1985), pp. 380-384. http://tinyurl.com/2y8t2b Also found a paper that mentions... Barnett (1976) and Small (1990) offer comprehensive surveys of different proposed alternative definitions of multivariate medians. Barnett, V. (1976) The ordering of multivariate data. Journal of the Royal Statistical Society A, 139(3), 318-344. Small, C.G. (1990) A survey of multidimensional medians. International Statistical Review, 58(3), 263-277. --Steve

2 1

[math-fun] mathematics of computer graphics on Ewetube...
by Henry Baker 04 Dec '07

04 Dec '07

Very high quality Scientific-American-level (PBS) discussion of some mathematics of computer graphics: http://video.google.com/videoplay?docid=8612534856516244040

1 0

[math-fun] extend exp(x) for quickly convergent Fourier series
by Greg Fee 04 Dec '07

04 Dec '07

Define a function f(x) on the interval -1 <= x < 0, to create a function g(x), such that: 1. g(x)=f(x) for -1 <= x < 0 2. g(x)=exp(x) for 0 <= x <= 1 3. The period 2 Fourier series of g(x) on the interval -1 <= x <= 1, of the form: a[0] + sum(a[i]*cos(i*Pi*x),i=1..infinity) + sum(b[i]*sin(i*Pi*x),i=1..infinity) converges to exp(x) on the interval 0 <= x <= 1, faster than choosing f(x)=exp(x) Can you find an f(x) such that g(x) has the quickest converging Fourier series to exp(x) on [0,1] ?

2 2

Re: [math-fun] n-D median redefined
by Fred lunnon 03 Dec '07

03 Dec '07

It's not at all obvious whether this function has multiple (local) minima --- in which case it may be nontrivial to compute. Almost certainly, the sum of the squares of the distances would be more tractable. What relation might these definitions bear to the convex hull stripping algorithm mentioned earlier? WFL On 12/3/07, Steve Witham <sw(a)tiac.net> wrote: > My friend Richard Harter redefined my median in what may be a nicer way: > > >We use the sum of absolute distances function, > > > >f(x) = sum(abs(x-x_i)) > > > >and find the set of x's such f(x) is a minimum. All of these > >are valid medians; however the centroid of the set is in some > >sense the most central median. > > --Steve > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

2 1

[math-fun] n-D median redefined
by Steve Witham 03 Dec '07

03 Dec '07

My friend Richard Harter redefined my median in what may be a nicer way: >We use the sum of absolute distances function, > >f(x) = sum(abs(x-x_i)) > >and find the set of x's such f(x) is a minimum. All of these >are valid medians; however the centroid of the set is in some >sense the most central median. --Steve

1 0

[math-fun] Submarine: prepare to be bored
by Steve Witham 03 Dec '07

03 Dec '07

I got the "combinations instead of cross products" optimization into my submarine hunt program. http://www.tiac.net/~sw/math-fun This "optimization" isn't always, because it tries moves in a different order. Here's a comparison of the previous and current methods, showing the number of search moves each took to prove or disprove that problem n could be solved in a certain number of time steps: prove disprove n nsteps old new old new __ ______ _____ _____ _____ _____ 2 3 4 2 2 2 2 3 5 8 8 4 7 9 * 4 7 13 37 * 6 137 91 5 9 19 15 8 2174 1343 6 11 7077 346 10 7072 2748 9 24744 14254 7 13 34 1105 12 6.2e6 1.1e6 8 15 43 64158 * 14 1.3e9 1.0e8 9 17 53 4.1e5 * 16 ? 5.8e9 10 19 4.6e8 1.6e6 18 4.4e8 8.2e7 17 4.0e8 3.4e9 * 16 1.1e11 1.1e10 11 21 76 >1.6e8 * One thing I hadn't anticipated was that because it picks the moves out of time order, if it succeeds in fewer shots than anticipated, the unused shot(s) may be in the middle of the time sequence: n=2, 2 shots, 3 time steps: 0 X 1 n=4, 6 shots, 7 time steps: 0 0 0 X 1 2 3 n=8, 14 shots, 15 time steps: 0 0 0 0 3 1 1 X 1 1 2 4 6 5 7 --Steve

1 0

Re: [math-fun] extend exp(x) for quickly convergent Fourier series
by Eugene Salamin 03 Dec '07

03 Dec '07

----- Original Message ---- From: Greg Fee <gfee(a)cecm.sfu.ca> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Monday, December 3, 2007 11:11:14 AM Subject: Re: [math-fun] extend exp(x) for quickly convergent Fourier series Greg Fee wrote: > Define a function f(x) on the interval -1 <= x < 0, > to create a function g(x), such that: > > 1. g(x)=f(x) for -1 <= x < 0 > 2. g(x)=exp(x) for 0 <= x <= 1 > 3. The period 2 Fourier series of g(x) on the interval -1 <= x <= 1, > of the form: > a[0] + sum(a[i]*cos(i*Pi*x),i=1..infinity) > + sum(b[i]*sin(i*Pi*x),i=1..infinity) > > converges to exp(x) on the interval 0 <= x <= 1, > faster than choosing f(x)=exp(x) > > Can you find an f(x) such that g(x) has the quickest > converging Fourier series to exp(x) on [0,1] ? If you are contented with a function that is continuous, but has discontinuous slope (so that a[n] ~ n^-2), then g(x) = exp|x| has the advantage of being symmetric. Thus you have only cosine terms. Gene ____________________________________________________________________________________ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

1 0

Re: To Greg Re: [math-fun] extend exp(x) for quickly convergent Fourier series
by Greg Fee 03 Dec '07

03 Dec '07

Dan Asimov wrote: > Hi, Greg. > > Interesting type of question! > > Do you have a specific way of measuring speed of convergence? > > Regards, > > Dan Asimov > We could choose the function, such that we need the fewest number of terms in the truncation of the Fourier series, so that the uniform norm of the difference between the Fourier "polynomial" and exp(x) is less than a given value epsilon, say epsilon=1/2^11 for "computer graphics" accuracy.

1 1

[math-fun] Strange answer
by Eric Angelini 03 Dec '07

03 Dec '07

http://www.cetteadressecomportecinquantesignes.com/AutoGooo.htm Best, É. (Dylan fan)

1 0

RE: [math-fun] Add first diff of digits and repeat
by Eric Angelini 03 Dec '07

03 Dec '07

Thanks a lot, Mike. EA: > Are there integers leading to infinite sequences? Mike: > no, you can never increase the number of digits. (...) --- Edwin Clark has kindly computed this: n = 1, max num iterations jump = 1, final value = 1 n = 10, max num iterations jump = 2, final value = 11 n = 12, max num iterations jump = 7, final value = 33 n = 18, max num iterations jump = 8, final value = 44 n = 100, max num iterations jump = 20, final value = 222 n = 200, max num iterations jump = 42, final value = 444 n = 201, max num iterations jump = 43, final value = 444 n = 1000, max num iterations jump = 377, final value = 4444 n = 10000, max num iterations jump = 2926, final value = 44444 n = 100000, max num iterations jump = 23541, final value = 444444 Best, É.

1 0