3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ "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? $\endgroup$
    – adam W
    Commented Mar 17, 2013 at 17:08
  • $\begingroup$ 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. $\endgroup$ Commented Mar 17, 2013 at 21:16
  • $\begingroup$ 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. $\endgroup$ Commented Mar 17, 2013 at 21:36
  • $\begingroup$ 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 :) $\endgroup$
    – adam W
    Commented Mar 17, 2013 at 23:54
  • $\begingroup$ If the smallest singular value were unique, do you see how to compute $\delta(A)$? $\endgroup$ Commented Mar 17, 2013 at 23:56

2 Answers 2

1
+50
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ Thanks @adamW. I'm going to have to go over this tomorrow. Looks interesting... $\endgroup$ Commented Mar 20, 2013 at 23:06
  • $\begingroup$ Thank you for introducing me to some nice ideas and for a creative solution. $\endgroup$ Commented Mar 23, 2013 at 18:13
1
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ Wow, the code does not seem to display. Does it show at least in the edit? $\endgroup$
    – adam W
    Commented Mar 25, 2013 at 23:45
  • $\begingroup$ here is the dropbox $\endgroup$
    – adam W
    Commented Mar 26, 2013 at 0:03
  • $\begingroup$ And the test script $\endgroup$
    – adam W
    Commented Mar 26, 2013 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .