New answers tagged

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)$$ ...
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 ...
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 ...
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 ...

Top 50 recent answers are included