   function k = WeakColumn(A)
 % A is an m-by-n matrix.
 % k satisfies 1<=k<=n and the minimum value of 
 %          norm( [A(:,1:k-1) A(:,k+1:n)]x - A(:,k) , 2)
 % is less than or equal to sigmin*sqrt(n) where sigmin is A's smallest singular value.
 
 [m,n] = size(A);
 [U,S,V] = svd(A);
 z = V(:,n);
 
 % Recall that || Az || = S(n,n). 
 % i.e,
 %         ||  z(1)A(:,1) + z(2)A(:,2) + ... + z(n)A(:,n) || = S(n,n)
 
 % Suppose |z(k)| = norm(z,inf). It follows that |z(k)|>= sqrt(n). Thus,
 % if inx = [1:k-1 k+1:n] and y = z(idx)/z(k) then
 
 %  ||  A(:,idx)y + A(:,k) || = S(n,n)/|z(k)| <= sqrt(n) S(n,n)
 
 % But  min || A(:,idx)x - A(:,k) || <= ||  A(:,idx)y + A(:,k) ||.
 
 [mu,k] = max(abs(z));
 
 % Up to -5  if you dont prove your method satisfies the bound.
 

