The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.research

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: peculiar min-max question
Replies: 1   Last Post: Aug 17, 2011 7:00 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Scheffler

Posts: 20
Registered: 12/11/06
peculiar min-max question
Posted: Aug 17, 2011 7:00 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


In research work on a certain statistical problem the following min/max
problem and the question of a fast algorithm came up:

Given n vectors x_1,...,x_n in R^d and denote by \|\theta\| the
Euclidian norm of \theta\in R^d. I would like to efficiently compute
(or at least approximate)

V_n=min_{\|\theta\|=1} \max_{1\leq i\leq n}|<x_i,\theta>|

where <x_i,\theta> denotes the ususal inner-product.

The brute-force approach works, sort of.... Here is what I tried:
Sample m independend and uniformly distributed \theta_j on the sphere,
compute the m\times n matrix of |<x_i,\theta_j>| and then find the
min/max of that matrix. This is easily done in MATLAB. However, n and
the dimension d (to have m small enough) have to be reasonable small...

Therefore I am looking for a different approach. For me it look's like a
problem in convex geometry or optimization....

Since I am not an expert in these fields of mathematics (me working
mostly in probability theory) I would appreciate any suggestions or remarks.

Many thanks!


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.