# Modification of a known optimization problem

In my research of linear algebra and optimization, I wish to modify the following well-known problem:

$\min \lVert x-Ax \rVert$ subject to $rank(A)\leq k$ where $x$ is a given column vector and we optimize over matrices of bounded rank.

My question is, can there be a way to solve the modified problem where the constraint is put on the norm (any matrix norm) of the matrix rather than its rank? I am not able to see a way to do this but perhaps it can be done or approximated. I thank all helpers.

• There exists a rank 1 matrix $A$ such that $Ax=x$. – Michael Renardy Dec 28 '17 at 14:05
• If you consider the operator norm with respect to the usual euclidean norm (assuming $\lVert\cdot\rVert$ is the Euclidean norm), then: if your norm bound is $1$ or greater, you can achieve the obvious minimum of zero (in many ways); if the bound $b$ is below $1$, the optimal choice is any $A$ that take $x$ to $bx$ and has operator norm $b$. So the problem seems solvable without any tool, unless I am mistaken. – Benoît Kloeckner Dec 29 '17 at 12:28
• Just as the above two commentators have pointed out, you should consider modifying your question or deleting it completely, as the answer is trivial. In most cases, when the number of free variables exceeds that of the known in a problem as it is in this question, it leads to a trivial answer. – Hans Jan 6 '18 at 20:04

## 1 Answer

This can be expressed (converted into) as a convex Second Order Cone Problem or SDP, depending on the norms used. CVX or another modeling tool can be used to convert the entered problem into a standard form for a solver. For example,

cvx_begin
variable A(m,n)
minimize(norm(x-A*x,p1))
norm(A,p2) <= bound_on_norm
cvx_end


p1 can be any number >= 1 or Inf (specifies p1-norm). p2 can be any of 1, 2, Inf, or 'fro' (Frobenius) to specify which norm to use. Or use norm_nuc instead of norm in the constraint to use nuclear norm.