## New answers tagged convex-optimization

3
votes

### For $f$ geodesically convex with $L$-Lipschitz-gradient on hyperbolic space, is $f(x)-f(x^*)\leq(\mathrm{const}) \cdot L r$ for all $x \in B(x^*, r)$?

The function $f$ has to be Lipschitz.
Assume contrary, choose a sequence of points $p_n$ such that $\lambda_n=|\nabla_{p_n}f|\to \infty$.
Let $$f_n(x)=\tfrac1{\lambda_n}\cdot f\circ m_n(x)-f(p_n)$$ ...

- 39.3k

0
votes

### Can one always find sparse solutions to an $\ell^1$-minimization problem?

It is true that one can always find an $m$-sparse solution.
If $\hat x$ is solution and $\|\hat x\|_0 \ge m+1$, one can perform a small gradient step (with respect to the L1 norm) in a neighborhood of ...

- 980

2
votes

### Eigenvectors that are tensor products?

Your $f(x) := \langle x^{\otimes r}, A x^{\otimes r}\rangle$ is a homogeneous polynomial of degree $2r$ of $d$ variables, $q(x) := ||x||^2$ is a homogeneous quadratic polynomial, and you look for the ...

- 178

3
votes

### Eigenvectors that are tensor products?

This is NP-hard already when $r = 2$. To see this, I will consider the problem of minimizing your function $f$ instead of maximizing it, but it's not too much work to flip things around to see that ...

- 5,078

3
votes

### Eigenvectors that are tensor products?

I strongly doubt any efficient algorithm exists for even approximately finding the maximizer in general. With slightly different notation, your problem is the same as the problem of "tensor ...

- 527

1
vote

Accepted

### Probability of accurate sparse recovery

A good starting point is "Mathematics of sparsity (and a few other things)" by E. Candes, or a book on compressed sensing such as "A Mathematical Introduction to Compressive Sensing&...

- 980

1
vote

Accepted

### Differentiability of some function defined as the maximum

Suppose that there is an open subset $U$ of $E$ such that the Lebesgue measure of $E\setminus U$ is $0$. Since $E$ is compact, the function $E^n\ni(x_1,\dots,x_n)\mapsto|y-x_i|^2$ is $L$-Lipschitz for ...

- 85k

Top 50 recent answers are included

#### Related Tags

convex-optimization × 733oc.optimization-and-control × 191

nonlinear-optimization × 166

convex-analysis × 135

linear-algebra × 112

linear-programming × 85

fa.functional-analysis × 78

convexity × 65

real-analysis × 54

convex-geometry × 54

global-optimization × 52

pr.probability × 41

reference-request × 40

matrices × 37

convex-polytopes × 36

semidefinite-programming × 32

na.numerical-analysis × 24

inequalities × 22

ca.classical-analysis-and-odes × 20

st.statistics × 19

probability-distributions × 18

combinatorial-optimization × 18

mg.metric-geometry × 17

duality × 17

computational-complexity × 16