1
$\begingroup$

Let $A\in \mathbb{R}^{m\times n}$, $m>n$, $rank(A)=n$, and $\forall 1 \leq i \leq m, 1 \leq j \leq n, A(i, j)>0$, $y=[1, 1, 1, ..., 1]^T$. Let $\beta=A(A^TA)^{-1}A^Ty$, how to prove that each element of $\beta$ is positive?

Actually, I have tried a lot of random simulation experiments of this question and no one exception has occured, but I don't know how to prove it theoretically. enter image description here

Here is the code:

'''

count = 0;

while count<1000000

  count=count+1;
  col=randi([2,20]);
  A = 100*rand(10000,col);
  [m,n] = size(A);
  random_order = randperm(m);
  A = A(random_order, :);

  Y=ones(m,1);

  W = inv(A'*A)*A'*Y; 
  y = A*W;
  numNegatives = sum(y < 0);
  miny=min(y);

  if numNegatives>0
      break
      A
  end
  fprintf("%dth,%d rows,%d columns, %d Negatives\n",count,m, n, numNegatives)

end

'''

Results:

'''

999989th,10000 rows,12 columns, 0 Negatives
999990th,10000 rows,18 columns, 0 Negatives
999991th,10000 rows,4 columns, 0 Negatives
999992th,10000 rows,16 columns, 0 Negatives
999993th,10000 rows,12 columns, 0 Negatives
999994th,10000 rows,5 columns, 0 Negatives
999995th,10000 rows,14 columns, 0 Negatives
999996th,10000 rows,5 columns, 0 Negatives
999997th,10000 rows,2 columns, 0 Negatives
999998th,10000 rows,20 columns, 0 Negatives
999999th,10000 rows,16 columns, 0 Negatives
1000000th,10000 rows,19 columns, 0 Negatives

'''

$\endgroup$
4
  • $\begingroup$ This is a scientific question, which seems simple but hard to proof in real. $\endgroup$ Commented Sep 7 at 4:19
  • $\begingroup$ I suppose you meant $\beta = A(A^TA)^{-1}A^Ty$ instead of $\beta = A(A^TA)^{-1}Ay$? Otherwise this makes no sense since $(A^TA)^{-1}$ is $n \times n$ but $A$ is $m \times n$. $\endgroup$
    – David Gao
    Commented Sep 7 at 5:10
  • $\begingroup$ You probably mean not $\beta=A(A^TA)^{-1}Ay$, but $\beta=A(A^TA)^{-1}A^Ty$, in agreement with your code and with common sense. I edited. $\endgroup$ Commented Sep 7 at 5:11
  • $\begingroup$ I am very grateful to you for pointing out this issue; it was a typo during my typing. $\endgroup$ Commented Sep 7 at 9:55

1 Answer 1

5
$\begingroup$

This does not hold in general.

Note that $\beta=A(A^TA)^{-1}A^Ty\in \mathbb{R}^m$ belongs to the image ${\rm Im} A$ (that is, to the column space of $A$). Also, $A^T\beta=A^TA(A^TA)^{-1}A^Ty=A^Ty$, so $A^T(y-\beta)=0$, in other words, $y-\beta\in \operatorname{Ker} A^T=(\operatorname{Im} A)^\perp$. Thus, $\beta$ is just the projection of $y$ to $\operatorname{Im} A$. Can it have non-positive coordinates? Of course, why not. You may construct a counterexample already for $m=3$ and $n=2$. It is natural to start with choosing the projection of $y$ to $\operatorname{Im} A$, let this vector $v_0:=(a, b, c)^T$ be such that with $a<0,b>1$ and $a+b+c=a^2+b^2+c^2$ (that yields $v_0-y\perp v_0$). For example, you may choose $a=1/100,b=1+1/100$ and find appropriate $c$. Then take two columns of $A$ as two arbitrary linearly independent vectors with positive coordinates which are orthogonal to the vector $y-v_0=(1-a, 1-b,1-c)^T$. Since the vector $y-v_0$ have coordinates of both signs, you can find such vectors

$\endgroup$
9
  • $\begingroup$ Thank you very much for your answer. I had also considered the idea you mentioned before. However, I think your answer is not entirely correct and can't disprove the conclusion. Here are the reasons: 1. $A$ is constrained, with each of its elements being greater than 0, ; $\endgroup$ Commented Sep 7 at 12:11
  • $\begingroup$ 2. It seems inappropriate to consider this problem from the perspective of $A^T \beta = A^Ty$. Beacause $A^T \beta = A^Ty$ and $\beta=A(A^TA)^{-1}A^Ty$ are not equivalent, one can conclude $A^T \beta = A^Ty$ from $\beta=A(A^TA)^{-1}A^Ty$, but can not conclude $\beta=A(A^TA)^{-1}y$ from $A^T \beta = A^Ty$. Actually, $A^Tx=A^Ty$ has infinitely solutions but $\beta$ is unique. $\beta$ is a subset of the solutions of $A^Tx=A^Ty$. Although there exist negative elements in the solutions of $A^Tx=A^Ty$, we can't conclude $\beta$ has negative elements. $\endgroup$ Commented Sep 7 at 12:13
  • $\begingroup$ For example, let $[1,2;3,4;6,7;2,1]$, then the solution of $A^T x = A^T$ is $x=a[3, -5, 2, 0]^T+b[5,-3, 0,2]^T+[-3, 5, 0, 0]^T$, existing negative elements obviously. However, $\beta=[0.4676, 0.6153, 1.4441, 0.8072]^T$ is unique. $\endgroup$ Commented Sep 7 at 12:13
  • $\begingroup$ Let's consider your questions one by one. $\beta$ is unique: it is the projection of $y$ to the space $X:={\rm Im} A$. This claim is equivalent to simultaneous conditions $\beta\in X$ and $y-\beta\in X^{\perp}$. I check both. Is this ok? $\endgroup$ Commented Sep 7 at 12:27
  • $\begingroup$ Yes, that's right. $\endgroup$ Commented Sep 7 at 13:24

You must log in to answer this question.

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