Approximate $\ell_{0}$-penalized estimation of piecewise-constant signals on graphs
图上分段常数信号的近似 ℓ₀ 惩罚估计AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要研究图信号恢复与通用惩罚估计，未涉及经济网络中的交互或干扰，现有细分证据不足。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
图上分段常数信号的近似 ℓ₀ 惩罚估计
- 研究问题
- 在图结构上恢复分段常数信号时，如何兼顾边稀疏估计的统计风险与计算可行性，并处理图连接结构的不均匀性？
- 方法与思路
- 作者采用 ℓ₀ 边惩罚目标，以多项式时间的 α-expansion 算法近似求解，并用有效电阻等连接性指标设置边权。
- 材料陈述的贡献
- 摘要称近似解可保持相同统计风险保证，并在指定稀疏类上达到极小极大最优速率；高信噪比实验显示较高精度。
- 阅读关注点
- 应核对近似解的定义、风险保证所需条件、平均顶点度的作用，以及加权稀疏类和总变差比较的具体范围。
- 阅读边界
- 仅据 OpenAlex 索引摘要，稿件版本未注明；摘要未给出风险界、算法精度条件或实验数值，不能推广为全面优于总变差估计。
原文摘要
We study recovery of piecewise-constant signals on graphs by the estimator minimizing an $l_{0}$-edge-penalized objective. Although exact minimization of this objective may be computationally intractable, we show that the same statistical risk guarantees are achieved by the $\alpha$-expansion algorithm which computes an approximate minimizer in polynomial time. We establish that for graphs with small average vertex degree, these guarantees are minimax rate-optimal over classes of edge-sparse signals. For spatially inhomogeneous graphs, we propose minimization of an edge-weighted objective where each edge is weighted by its effective resistance or another measure of its contribution to the graph’s connectivity. We establish minimax optimality of the resulting estimators over corresponding edge-weighted sparsity classes. We show theoretically that these risk guarantees are not always achieved by the estimator minimizing the $l_{1}$/total-variation relaxation, and empirically that the $l_{0}$-based estimates are more accurate in high signal-to-noise settings.