Matrix infinity norm over rows

[patwa67]

Is there some way to implement the induced infinity matrix norm:
maximum absolute row sum of a matrix
Lets say I have multivariate data in Y (for simplicity of dim n x 2) and X, and want to solve:

@minimize ls( A*X - Y ) + λ[1]*norm(X[:,1],1) + λ[2]*norm(X[:,2],1) + λ[3]*"maximum absolute row sum of matrix X"

[nantonel]

You can minimise infinity norm over the i-th row using norm(X[:,i],Inf).

However having:

@minimize ls( A*X - Y ) + norm(X[:,1],1) + norm(X[:,2],1) + norm(X[1,:],Inf) + norm(X[2,:],Inf) + ...

won't be accepted because there's no efficiently computable proximal mapping. See the documentation.

I'm not aware if there's an efficient proximal mapping for that particular mixed norm....

[nantonel]

BTW the following notation can be used to construct such cost functions:

@minimize ls(A*X-b)+sum(norm(X[i,:],Inf) for i =1:size(X,1))

[lostella]

I think the issue title here is misleading: what is needed is (warning: pseudocode follows) maximum(norm(X[i,:], 1) for i in 1:size(X, 1))

[patwa67]

Yes you're right. However, I cannot get it to work:

using StructuredOptimization
#Simulated data (n observations, p variables, tr truevariables, sig error)
n, p, q, tr_p1, tr_p2, sig = 1000, 5000, 2, 10, 5, 0.5
A = randn(n, p)
Y = randn(n, q)
X_true1 = [randn(tr_p1)..., zeros(p-tr_p1)...]
X_true2 = [randn(tr_p2)..., zeros(p-tr_p2)...]
y1 = A*X_true1 + sig*randn(n)
y2 = A*X_true2 + sig*randn(n)
Y[:,1] = y1
Y[:,2] = y2
λ1, λ2, λ3 = 0.1, 0.1, 0.1
X = Variable(size(A)[2],size(Y)[2])

@minimize ls(A*X - Y) + λ1*norm(X[:,1],1) + λ2*norm(X[:,2],1) + λ3*(maximum(norm(X[i,:],1)) for i in 1:size(X,1)) with ZeroFPR();# solve problem

leads to:

ERROR: MethodError: no method matching *(::Float64, ::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##9#10"))})
Closest candidates are:
  *(::Any, ::Any, ::Any, ::Any...) at operators.jl:502
  *(::Float64, ::Float64) at float.jl:399
  *(::AbstractFloat, ::Bool) at bool.jl:120
  ...
Stacktrace:
 [1] top-level scope at none:0

[nantonel]

You can view this operation as a mixed norm, possibly named as $l_{1,Inf}$, however currently only the sum of l2 norms is available, that is $l_{2,1}$. See documentation.

As stated above I don't know if there exist an efficient implementation of the proximal mapping of the $l_{Inf,1}$ norm.

Currently, maximum works only when its input is a Variable.

[nantonel]

In case we had an efficient proximal mapping of the l_{1,Inf} norm I don't think we would go for this syntax:

maximum(norm(X[i,:], 1) for i in 1:size(X, 1))

but rather:

norm(X,Inf,1; dim=1)

Although it would be cool to have the former! 😄

[lostella]

@nantonel the best would be to have opnorm(X, Inf) directly

[patwa67]

Are you planning to implement support for opnorm?