# Tagged Questions

1answer
45 views

0answers
35 views

### Total Variation minimization problem

Thanks for reading this thread. I have a object function, with constraints, I am trying to minimize. The object function is the Total Variation of an image. The Total Variation is defined as: ...
1answer
105 views

### What minimizes the Chebyshev Distance?

For an arbitrary number of dimensions, I know that the mean minimizes the distance using the L2 norm and that the geometric median minimizes the distance function using the L1 norm (though I have yet ...
0answers
48 views

### Distance metrics with kmeans

Context: I'm trying to derive some formulas for computing the "mean" in the K-means algorithm. So given an assignment of $m$ data points to $k$ clusters, find a formula to recompute the mean of the ...
1answer
25 views

### Analytical solution to fitting two functions

I have two oscillatory functions $f(x)$ and $(k x)^2 g(x)$ where $f$ and $g$ are known and it is also known that the two functions are approximately similar. How can I analytically find the best ...
1answer
122 views

### Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
1answer
37 views

### A question on minimizing $\| . \|_2^2$ vs $\| . \|_2$

Suppose we are in $\mathbb{R}^n$ Is the problem of $d(x,Y) = \inf\{ \| x - y\|^2 : y \in Y\}$ equivalent to $d(x,Y) = \inf\{ \| x - y\| : y \in Y\}$ Pardon me, let us keep it simple and just stick ...
1answer
110 views

### L1-norm minimization

This is undoubtedly a trivial question but might as well ask: Why is the L1 norm minimization a heuristic for finding the sparsest vector? What I mean is that if the L1 norm sums the elements of a ...
0answers
61 views

### How to solve an optimization problem with non-convex Frobenius norm constraint?

The form of my problem is: $$\min_W \|Y-WX\|_F^2-\|V-WU\|_F^2$$ $$s.t. \|W\|_F=1$$ All five variables are matrices. Since the norm constraint is a non-convex one, I have no idea how to solve this ...
2answers
144 views

### How is $L_{2}$ Minkowski norm different from $L^{2}$ norm?

I am reading the book Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition. They use $L_{2}$ Minkowski norm (Euclidean) as the distance metric in the feature space ...
1answer
121 views

### Low-rank matrix approximation in terms of entry-wise $L_1$ norm

According to the Eckart–Young theorem, the low-rank matrix approximation problem $$\min_{\tilde{A}} \quad \| A - \tilde{A} \|_F \quad \text{s.t.} \quad \text{rank}(\tilde{A}) \le r$$ is given by the ...
0answers
40 views

1answer
671 views

### Constrained infinity norm minimization

I have a problem like this: $$\min_x |Ax|_\infty \text{ s.t. } \sum_i x_i = c$$ That is, I want to find the vector $x$ whose elements sum to a constant $c$ that minimized the infinity norm of $Ax$. ...
1answer
117 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 ...
0answers
57 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 ...
2answers
150 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 ...
2answers
209 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 ...
0answers
107 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$ ...
1answer
113 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*} ...
0answers
225 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 ...
0answers
131 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 ...
1answer
307 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 ...
2answers
78 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$ ...
0answers
171 views

1answer
381 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 ...
1answer
316 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 ...
1answer
155 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 ...
1answer
548 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) ...