The problem of locating repetitive unknown motifs in signals appears ubiquitously in neuroscience, computational imaging, microscopy data analytics, and more. We cast this problem as a short-and-sparse blind deconvolution problem, and formulate it as a nonconvex optimization problem over the sphere. By studying the geometric structure of the nonconvex landscape, we show how to develop practical optimization methods, that solves the problem to the target solution up to a shift ambiguity. The new geometric insights lead to new optimization strategies that even works in very challenging regimes
joint work with Diego Klabjan, Youngseok Kim
Several machine learning models can be formulated as maximization of a scale invariant function under a Euclidian ball constraint, for example, PCA, GMM, NMF. We generalize power iteration to this setting and analyze convergence properties of the algorithm. Our main result states that if initialized close to a local maximum, then the algorithm converge to this local maximum. Also, the convergence rate is linear and thus equal to the rate of power iteration. Numerically, we benchmark the algorithm against state-of-the-art methods to find out that the algorithm outperforms benchmark algorithms.
joint work with Drosos Kourounis, Olaf Schenk
A continuous reformulation of the traditional spectral method for the bi-partitioning of graphs is presented, that exploits the tendency of the p-norm to promote sparsity, thus leading to partitions with smaller edgecuts. The resulting nonlinear and non convex graph p-Laplacian quotient minimization is handled with an accelerated gradient descent, while a continuation approach reduces the p-norm from a 2-norm towards a 1-norm. The benefits of our scheme are demonstrated in a plethora of complex graphs emerging from power networks and social interactions.