0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ There exists a rank 1 matrix $A$ such that $Ax=x$. $\endgroup$
    – Michael Renardy
    Commented Dec 28, 2017 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
    Commented Dec 29, 2017 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
    Commented Jan 6, 2018 at 20:04

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .