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.

  • 1
    $\begingroup$ There exists a rank 1 matrix $A$ such that $Ax=x$. $\endgroup$ – Michael Renardy Dec 28 '17 at 14:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Benoît Kloeckner Dec 29 '17 at 12:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Jan 6 '18 at 20:04

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,

variable A(m,n)
norm(A,p2) <= bound_on_norm

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.