Tagged Questions
0
votes
0answers
22 views
L1 penalty can serve as a convex surrogate for an L0 penalty. Why?
I have heard machine learning practitioners say that the $L_1$ penalty is a (or can serve as) convex surrogate for an $L_0$ penalty (in the context of optimization and statistical fitting).
What do ...
0
votes
1answer
73 views
Difference between maximizing matrix's $l1$ norm and Frobenius norm
The original problem is to maximize the Frobenius norm of a matrix product
$max_{X\in \mathbb{D}}||B^TXA ||_F$, $\mathbb{D}$ is the doubly stochastic matrix set
As this is too difficult due to ...
1
vote
1answer
38 views
On norm selection for the solution of an overdetermined linear system
I am considering the following linear system:
$Ax = b$
Where:
$A$ is $9000 \times 139$
$x$ is $139 \times 1$ and sparse
$b$ is $9000 \times 1$
Most of the resources I have found online point to ...
1
vote
0answers
43 views
Optimizing over norms of set of equations.
I have a set of N real-valued finite-dimensional vectors $\mathbf{v}_i$ and target norms $y_i$ and I am trying to find a linear transformation matrix $L$ such that the norm of the transformed vectors ...
1
vote
2answers
54 views
minimizing a norm and a linear function
Let $y,\lambda\in\mathbb{R}^n$. I want to minimize the following with respect to $y$.
$$
f(y)=||y|| + \lambda^Ty
$$
where $||y||$ is the Euclidean norm. I first take the derivative of the function and ...
2
votes
2answers
80 views
Derive steepest descent vector subject to norm constraint
I am currently working through an old textbook Practical Optimization by Gill, Murray and Wright (c 1982) who make some derivations which seem correct, but I am unable to duplicate. In the equations ...
1
vote
0answers
59 views
How to represent and handle eigenvalue constraint in optimization
For example consider the problem
$\min_X f(X)$
s.t. $\lambda_i(X+A)=\lambda_i(B)$ for $i \in {1,...,N}$
where $A$ and $B$ are full rank N by N matrix, $\lambda_i(X)$ is the i-th eigenvalue of $X$
...
0
votes
1answer
60 views
What does RMSD mean?
Normally a rigid superposition which minimizes the RMSD is performed, and this minimum is returned. Given two sets of points and , the RMSD is defined as follows:
$$\begin{align*}
...
3
votes
0answers
144 views
Minimizing maximum absolute column sum norm of the residual between a matrix and its $k$-rank approximation
Let $X \in \mathbb{R}^{m\times n}$ be a matrix with rank $r$.
How can we find the optimal $\tilde{X} \in \mathbb{R}^{m\times n}$ whose rank is $k$ where $k\leq r$ and the reconstruction error in ...
1
vote
0answers
95 views
Upper bound for L1-L2 optimization problem
I am interested in the following convex optimization problem:
\begin{align*}
\max & ||x||_1 \\
\text{s.t.} & ||x-a||_1 \le K \\
& ||b\circ x||_2 \le 1\\
& x \in R^n
\end{align*}
where ...
2
votes
1answer
176 views
Symmetrically make this matrix orthogonal, but don't you dare use the Frobenius norm…
I have read many of the questions already here in regards to the Frobenius norm, but they do not help me too much.
My question is, why is the Frobenius norm not considered a 'proper' norm?
In a ...
0
votes
2answers
63 views
$l_1$ norm projection with regularization term
I recently encountered an optimization problem and looking for some technical paper for the same.The problem is give as below,
$\min f(x)+\lambda*r(x) $
$\ s.t \ x \geq 0, ||x||_1 = 1$.
where $x$ ...
0
votes
0answers
143 views
Supremum of constrained $L_1$ norm
For a fixed $\mathbf{h}$ in a subset of $\mathbb{C}^m$ such that $\mathbf{h}(k)\neq 0$ for any $k=0,...,m-1$, how can I find
$\sup_{\mathbf{x}} \{ \| \mathbf{x} \|_1 \,\,\, \mathrm{ s.t. } \,\,\, ...
1
vote
0answers
77 views
constrained optimization of dot product
Given a real matrix $A$ find a positive vector $x$ of unit length ($x^T x = 1$) for which $x^T A^T A x$ is minimal (closest to $0$).
A has size about $1000 \times 20$ and can be written as $[ A_P | ...
3
votes
1answer
210 views
Minimize distance between 2 functions
Just so you know, this is a homework question, and I basically need help with the steps to solve this problem. I understand what it's asking; however, my attempts haven't worked out, and I'm probably ...
7
votes
1answer
210 views
Maximum subset sum of $d$-dimensional vectors
This is a $d$-dimensional generalisation of the post Inequality with Complex Numbers. (See my comment under Robert Israel's answer.)
Generalising Potato's proof for $d$-dimensions, we can show the ...
0
votes
1answer
118 views
parametrize hypersphere
I want to find an $n$-vector $\hat{\theta}$ that maximizes a function $f(\theta)$ subject to the $p$-norm constraint $||\theta||_p = c$.
Is there a general parametrization of $p$-norm hyperspheres ...
2
votes
1answer
398 views
Projecting onto vector space with L-Infinity norm/ minimum absolute value polynomial fitting
I'm looking for a way to project a vector (in this case a function on the real line) onto a basis for that space (in this case the set of N-degree polynomials over the domain of a closed interval) ...
