ChapterZero

%% [X,Y,VAL] = INF1NORM(A) provides a probabilistic lower bound on the
% infinity->1 operator norm of A, to within a guaranteed factor, in
% expectation.
%
% (since the quality of the approximation is only guaranteed in
% expectation, you should call several times and retain the highest VAL and
% the corresponding X,Y)
%
% given a positive semidefinite matrix A, approximates the infinity->1 
% operator norm of A to, on average, within a factor of at least 0.56 and 
% returns the approximation as VAL. X is a sign vector satisfying 
% VAL = X.'*A*X; Y=X.
%
% if A is not PSD, returns an approximation that is on average within a factor 
% of at least .27, and X,Y are sign vectors satisfying VAL = X.'*A*Y;
%
% Reference: Alon and Naor. Approximating the Cut-norm via Grothendieck's
% Inequality.
 
function [x, y, val] = approxinf1norm(A)
 
[n,m] = size(A);
if n==m && all(eig(A) > 0)
    cvx_begin
        variable W(n,n) symmetric;
        maximize(trace(A*W));
        subject to
            diag(W) == ones(n,1);
            W == semidefinite(n);
    cvx_end
 
    G = randn(n,1);
    R = chol(W);
    x = sign(R.'*G);
    y = x;
    val = x.'*A*x;
else
    cvx_begin
        variable W(n+m,n+m) symmetric;
        maximize(trace([zeros(n,n) A; A.' zeros(m,m)]*W));
        subject to
            diag(W) == ones(n+m,1);
            W == semidefinite(n+m);
    cvx_end
 
    G = randn(n+m,1);
    R = chol(W);
    U = R(:, 1:n);
    V = R(:, n+1:end);
 
    x = sign(U.'*G);
    y = sign(V.'*G);
    val = x.'*A*y;
end   
 
end