EUVIMEDEUVIMED entdecken
Crossref

Proximity Operator of the $$\ell _1$$ over $$\ell _2$$ Function

Lixin Shen, Guohui Song

Journal of Optimization Theory and Applications · 2026-11 · 211 (2)

DOI: 10.1007/s10957-026-03151-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Optimization Theory and Applications, online erschienen am 09.11.2026. Verfasst von Lixin Shen und 1 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Gefördert von: Division of Mathematical Sciences.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the complete, possibly set-valued proximity operator of the nonconvex, scale-invariant ratio h(x)=‖x‖1/‖x‖2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h(\varvec{x})=\Vert \varvec{x}\Vert _{1}/\Vert \varvec{x}\Vert _{2}$$\end{document}. A polar decomposition of the nonzero branch, followed by sign and permutation reductions, transforms the proximal problem into a smooth rank-one quadratic problem over the nonnegative orthant of the unit sphere. After the magnitudes of the data are sorted, every canonical proximal direction belongs to a finite candidate set indexed by its support size k∈{1,…,n}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\in \{1,\ldots ,n\}$$\end{document}. For each k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document}, a candidate exists if and only if an explicit quartic equation has a simple root satisfying both a positive-orthant condition and a second-order derivative condition. This characterization eliminates the need to guess the unknown sparsity. We further derive a necessary-and-sufficient O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1)$$\end{document} prefix test that enforces positivity and prunes support sizes for which no candidate can exist. Using prefix sums, the optimized method performs an O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n)$$\end{document} scan after an O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} sorting step; the construction of multiple tied outputs is necessarily output-sensitive. Numerical experiments illustrate the finite-candidate selection, identify inputs on which a sparsity-guessing baseline is suboptimal, quantify the benefit of pruning, and demonstrate the numerical accuracy of the secular-equation solver. The observed runtimes exhibit near-linear growth over the tested range, consistent with the predicted O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n)$$\end{document} post-sorting scan and O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} total complexity.

Förderung

  • Division of Mathematical Sciences

Zitieren

APA

Shen, L., & Song, G. (2026). Proximity Operator of the $$\ell _1$$ over $$\ell _2$$ Function. Journal of Optimization Theory and Applications, 211(2). https://doi.org/10.1007/s10957-026-03151-7

Vancouver

Shen L, Song G. Proximity Operator of the $$\ell _1$$ over $$\ell _2$$ Function. Journal of Optimization Theory and Applications. 2026;211(2). doi:10.1007/s10957-026-03151-7

BibTeX
@article{Shen2026,
  author = {Shen, Lixin and Song, Guohui},
  title = {Proximity Operator of the $$\ell _1$$ over $$\ell _2$$ Function},
  journal = {Journal of Optimization Theory and Applications},
  year = {2026},
  volume = {211},
  number = {2},
  doi = {10.1007/s10957-026-03151-7}
}
Kostenlos starten →