A3 Solutions

P1

  function v = Nearest1(A,b)
% A is m-by-n and assume rank(A) = n < m.
% v is the nearest vector to b in the orthogonal complement of Ran(A)

[m,n] = size(A);
[Q1,R] = qr(A,0);

% If A = QR then Q = [Q1 Q2] where Q1 has n columns and Q2 has m-n columns.
% Note that Ran(Q2) is the orthogonal complement of Ran(A) = Ran(Q1).
% Must solve min norm(Q2*z - b). This
% has solution z = Q2'*b. Thus v = Q2*Q2'*b = (I - Q1*Q1')*b = b - Q1*Q1'b

v = b - Q1*(Q1'*b);

%-----------------------------------------------------------------------
% GRADING SCHEME
% --------------
%  3 pts for correctness
%  2 pts for efficiency. Pts deducted if using more than O(m*n^2) time,
%        e.g. by using full QR instead of skinny QR.
%-----------------------------------------------------------------------
 

P2

  function [x,y] = LSSum(A,B,alfa,c)
% A, B, and c are p-by-1 cell arrays.
% For i=1:m, A{i} and B{i} are m-by-n matrices and c{i} is m-by-1.
% alfa is a column p-vector with positive entries.
% x and y are column n-vectors that minimize
%
%   alfa(1)*|| A{1}x +  B{1}y - c{1} ||^2  + ... + alfa(p)*|| A{p}x +  B{p}y - c{p} ||^2
%
% Assumes that x and y are unique.

% Suppose p = 2. Then the problem to solve is the minimization of

%           sqrt(alfa(1))A{1}   sqrt(alfa(1))B{1}     x          sqrt(alfa(1))c{1}
%           sqrt(alfa(2))A{2}   sqrt(alfa(2))B{2}     y     -    sqrt(alfa(2))c{2}
%           sqrt(alfa(3))A{3}   sqrt(alfa(3))B{3}                sqrt(alfa(3))c{3}  
%

p = length(A);
[m,n] = size(A{1});
M = [];
b = [];
for i=1:p
    M = [M; sqrt(alfa(i))*[A{i}  B{i}]];
    b = [b;sqrt(alfa(i))*c{i}];
end
z = M\b;
x = z(1:n);
y = z(n+1:2*n);

%-----------------------------------------------------------------------
% GRADING SCHEME
% --------------
%  2 pts for correct setup of "M" matrix
%  2 pts for correct set up of "b" vector
%  1 pts for overall correctness
%-----------------------------------------------------------------------


 
 

P3

   function [Q,v] = MinPhi(A,B)
 % A and B are m-by-n matrices with n<=m.
 % Q is an n-by-n orthogonal matrix and v is a column n-vector with the
 % property that norm( (A - (B + e*v')Q,'fro' ) is minimized where e = ones(m,1).
 
 % Since 
 %               norm(A - (B + e*v')*Q,'fro')^2 = norm( (A*Q' - (B + e*v'),'fro')
 %                                              = norm( (A*Q' - B) - e*v'),'fro')
 %
 % we conclude that vopt = (1/m)*(A*Q' - B)'*e = (Q*(A'*e) - B'*e)/m
 %
 % Thus, (A*Q' - B) -e*vopt' = (A*Q' - B) - (1/m)*e*e'*(A*Q' - B)
 %                           = P*(A*Q' - B)   
 %
 % where P = (I - (1/m)*e*e'. Therefore, we seek an orthogonal Q that minimizes
 %
 %              norm(P*(A*Q' - B),'fro') = norm( P*(A - B*Q),'fro') = norm( A0 - B0*Q,'fro')
 %
 % where A0 = P*A and B0 = P*B. If U*S*V' = A0'*B0 is the SVD, then Qopt = V*U'.
 
   [m,n] = size(A);
   e = ones(m,1);
   A0 = A - (e/m)*(e'*A);
   B0 = B - (e/m)*(e'*B);
   [U,S,V] = svd(A0'*B0);
   Q = V*U';
   v = (Q*(A'*e) - B'*e)/m;
   
%-----------------------------------------------------------------------
% GRADING SCHEME
% --------------
%  5 pts for correctness
%  -1.5 if not using direct method (i.e. solve with iterative method).
%-----------------------------------------------------------------------

  

P4

    function [alfa,beta,gamma,Predict] = TrigLS(tau,f,P,n)
  % tau and f are column m-vectors, P is a positive real, and 
  % n is a positive integer (2n+1<=m).
  % Determines alfa (scalar), beta (column n-vector), and gamma (column n-vector)
  % so that if
  %
  %       F(t) = alfa +  sum_{k=1:n} of (beta(k)cos(2pi*k*t/P) + gamma(k)*sin(2*pi*k*t/P) )
  % then
  %       sum_{i=1:m} of ( F(tau(i)) - f(i) )^2
  %
  % is minimized. 
  % Predict is the column m-vector F(tau), i.e., Predict(i) = F(tau(i)), i=1:m.
  
  m = length(tau);
  A = ones(m,2*n+1);
  
  for k=1:n
      tVec       = (2*pi*k/P)*tau;
      A(:,k+1)   = cos(tVec);
      A(:,k+1+n) = sin(tVec);
  end
  x = A\f;
  Predict = A*x;
  alfa = x(1); beta = x(2:n+1); gamma = x(n+2:2*n+1);
  
%-----------------------------------------------------------------------
% GRADING SCHEME
% --------------
%  5 pts for correctness
%-----------------------------------------------------------------------