Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a tall matrix that is not rank-deficient and has normalized columns. That is $A$ is $m\times n$, $m<n$ and rank$(A)=m$, and $||a_i||_2=1$ for all columns $a_i$.

Define $$\delta_v(A):=\max_i \ \frac{|\langle a_i,v\rangle|^2}{||v||_2^2}.$$

Let $$\delta(A):=\inf_v\ \ \delta_v(A).$$

This is called the "decay factor" in some places. Is there a natural way to compute this? For an orthogonal matrix it is clear that $\delta$ is $1/n$. I tried to incorporate SVD and relate $\delta$ to the minimum singular value, but didn't get anywhere.

Alternatively, the problem may be stated as finding the infimum of $\frac{||A^tv||_\infty^2}{||v||_2^2}$, which is related to the problem of finding the smallest eigenvalue of $AA^t$. So might there be a way to find $\delta$ by studying $AA^t$?

EDIT: In plain English, the question is: given a set of $n>m$ unit vectors that span $\mathbb{R}^m$, how can one find the vector $v$ having the property that the angle between it and the "closest" unit vector (closest in angle) is as large as possible. Essentially, how can one find the vector farthest away from all of the other vectors.

share|improve this question
    
"I tried to incorporate SVD and relate δ to the minimum singular value, but didn't get anywhere"--seems to me that should work. The answer is the singular vector associated with the smallest singular value. This singular value is also the square root of the smallest eigenvalue of $AA^t$ (or $A^t A$). Can you expand on how or why your approach did not work? –  adam W Mar 17 '13 at 17:08
    
I abandoned this route because I realized that $\delta(A)$ couldn't be the smallest singular value itself, since for instance for orthogonal matrices $\delta(A)=1/n$, but the singular values are all 1. I didn't conjecture that the $v_r^T$ associated to the smallest singular value would work here. What I tried was using the low rank approximation to find a lower bound, but didn't get anywhere. –  Lepidopterist Mar 17 '13 at 21:16
    
I may be making a mistake, but it seems I'm able to contradict your answer, @adamW. We are seeking $$\inf_{||v||=1}||A^Tv||_\infty^2=\inf_{||v||=1}||\sum_1^r\sigma_i u_i v_i^Tv||_\infty^2.$$ Since the $v_i$'s span the column space of $A^T$, it follows that if we were dealing with the $l_2$ norm this sum is minimized when $v=v_r$. However, we are dealing with the $l_\infty$ norm, so if we take some small amount of the energy of $v=v_r$ and put it into $v_{r-1}$, we should be able to make the max entry a bit smaller. –  Lepidopterist Mar 17 '13 at 21:36
    
I am just realizing the case when the smallest singular value/vector is not unique. I think in that case your decay factor is unique, but the vector is not. And I thought the question was the $l_2$ norm. That and I don't believe that I fully understand the question, hence my commenting rather than answering :) –  adam W Mar 17 '13 at 23:54
    
If the smallest singular value were unique, do you see how to compute $\delta(A)$? –  Lepidopterist Mar 17 '13 at 23:56
show 3 more comments

2 Answers

up vote 1 down vote accepted
+50

The Question: $$\inf_{ ||v||_2 = 1}||v^\top A||_{\infty}$$

The solution to this has a similar flavor as the simplex algorithm. The simplex algorithm deals with a convex region in n-dimensional space defined by the hyperplanes given from the inequalities of the original problem. This question deals with the infimum of the infinity norm. Just as the best solution to the simplex is one of the vertices of the convex region (called the simplex), the solution here is a vertex of a hyper-cube. The difference here is that the hypercube varies, depending on the vector for which the infinity norm the box represents.

Insert here image of vector in 2-d with box around it representing the max value of the vector's elements, with the box having smallest size when the vector rotates so that the box's corner and the vector meet.

My Answer:

Overview: To get within 90 degrees in every dimension of the desired vertex, start with the vector found through use of the SVD. The minimum singular value's vector is that vector. From there "follow" the surfaces and edges of the bounding box (hyper-cube) until the vertex is reached. The end result is a row $r$ with the following properties: $r$ has $m$ distinct elements of equal magnitude each with a value of $||r||_{\infty}$. That is, those $m$ values are the maximal value in $r$.

  1. Use the SVD to unitarily rowmix $A$ so as to have one row as described (the minimum SVD vector). Call this row the candidate row. Find the largest value or values in the row, denote those indices as $i$, and call them the box-points.
  2. Perform Householder or Givens on the other rows (not using the candidate row) so that only one row has non-zero element(s) in the box-point indices $i$, and also with matching sign relative to the box-points. Below in the section labeled "box rotation" is a description of how to achieve this. Call this row the reduction row.
  3. Find the best Givens rotation between the candidate row and the reduction row that lowers the values of the box-points. This will necessarily result in another point becoming larger to the point of becoming a box-point.
  4. Repeat steps 2 and 3 until there are no more rows with which to build a reduction row. The algorithm is finished.

Box Rotation To obtain a row with values equal in desired indices, use the basic operation I call a box rotation.

$$\pmatrix{\gamma & \sigma \\ -\sigma & \gamma}\pmatrix{a & b \\ c & d} = \pmatrix{\star & \star \\ z_0 & z_0 \\} \tag{1}$$ $$\pmatrix{\gamma & \sigma \\ -\sigma & \gamma}\pmatrix{a & b \\ c & d} = \pmatrix{\star & \star \\ z_0 & -z_0 \\} \tag{2}$$ (1) requires solving $$-\sigma a + \gamma c= -\sigma b + \gamma d = z_0$$ which simply gives $$ \frac{\sigma}{\gamma} = \frac{d-c}{b-a} $$

(2) requires solving $$-\sigma a + \gamma c= \sigma b - \gamma d = z_0$$ which simply gives $$ \frac{\sigma}{\gamma} = \frac{d+c}{b+a} $$

From here the idea is to keep a set of equal and maximal values that are ever diminishing until all the rows are exhausted. If $m$ maximal values in the row are achieved, then the row represents the corner of a hyper-cube, thus is the smallest possible in the infinity norm.

Here is a "silent description" of how to use the box rotation to find the edge of the hypercube described by the first three elements being equal in magnitude:

\begin{align} \pmatrix{\star & \star & \star \\ \star & \star & \star \\\star & \star & \star\\} \overset{\text{QR}}{\rightarrow} \pmatrix{\star & \star & \star \\ 0 & \star & \star \\ 0 & 0 & \star\\} \overset{\text{box-1}}{\rightarrow} \pmatrix{\star & \star & \star \\ a & a & \star \\ 0 & 0 & \star\\} \overset{\text{box-2}}{\rightarrow} \pmatrix{\star & \star & \star \\ \star & \star & \star \\ b & b & b \\}\\ \end{align}

share|improve this answer
    
Thanks @adamW. I'm going to have to go over this tomorrow. Looks interesting... –  Lepidopterist Mar 20 '13 at 23:06
    
Thank you for introducing me to some nice ideas and for a creative solution. –  Lepidopterist Mar 23 '13 at 18:13
add comment

I liked this question because to me it was a good balance of challenge vs. reward. Here is my Python code that gives pleasing results. Note that it works only when the singular value decomposition is performed in the place that I commented. Otherwise it is only mediocre. Class Box is basically just a matrix along with the key functions. A test script using the functionality follows.

import math
class Box:
  def __init__(self,rows,cols):
    self.rows=rows
    self.cols=cols
    self.rowrange=range(self.rows)
    self.colrange=range(self.cols)
    self.row=[[0 for i in self.colrange] for j in self.rowrange]
    for i in self.rowrange:
      self.row[i][i]=1
    self.epsilon = 1e-10
  def givens_dn(self, ir, ic):
    for r in range(ir+1, self.rows):
      if abs(self.row[r][ic]) 

Here is the test script

from Box import *
import random
import time

def dot(x,y):  return sum(map(lambda a,b:a*b,x,y)) # dot product of x and y

dim=60
num = 120

print("inf of the infinity norm; unit vector furthest from other unit vectors")
print("----------------------------------------------------------------------")
print("File: TEST_Box.py")
print(time.ctime())
print("dim=", dim)
print("num=", num)
seed = time.time()
random.seed(seed)
print("seed=",seed)

v = Box(dim, num)

for j in  v.colrange:
  nn=0
  for i in v.rowrange:
    val = random.random()*2 - 1 # random real in [-1,1]
    v.row[i][j] = val
    nn+=val*val
  n = math.sqrt(nn)
  for i in v.rowrange: v.row[i][j]/=n # normalized columns

# SVD needed here, set first row as the smallest
print("******For best results SVD needed here; set first row as the smallest******")

bmx = max(v.row[0],key=lambda x:abs(x))

boxpoint =[v.row[0].index(bmx)]
v.givens_dn(1,boxpoint[-1])
boxpoint.append(v.red_box(0,1,boxpoint[-1]))
bmx2 = max(v.row[0],key=lambda x:abs(x))
print("First box reduction \t %f -->  %f"%(bmx,bmx2))

r=2
while r
share|improve this answer
    
Wow, the code does not seem to display. Does it show at least in the edit? –  adam W Mar 25 '13 at 23:45
    
here is the dropbox –  adam W Mar 26 '13 at 0:03
    
And the test script –  adam W Mar 26 '13 at 0:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.