Computing the decay factor for a full rank wide matrix, or finding a unit vector farthest away from a set of spanning unit vectors

Question

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.

Answer 1

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}

Answer 2

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