ML Anthology

Rank, Trace-Norm and Max-Norm

Nathan Srebro, Adi Shraibman
COLT 2005 pp. 545-560
doi:10.1007/11503415_37 /colt/2005/srebro2005colt-rank/

Abstract

We study the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity. We present generalization error bounds for predicting unobserved entries that are based on these measures. We also consider the possible relations between these measures. We show gaps between them, and bounds on the extent of such gaps.

PDF COLT Semantic Scholar

Cite

Text

Srebro and Shraibman. "Rank, Trace-Norm and Max-Norm." Annual Conference on Computational Learning Theory, 2005. doi:10.1007/11503415_37

Markdown

[Srebro and Shraibman. "Rank, Trace-Norm and Max-Norm." Annual Conference on Computational Learning Theory, 2005.](https://mlanthology.org/colt/2005/srebro2005colt-rank/) doi:10.1007/11503415_37

BibTeX

@inproceedings{srebro2005colt-rank,
  title     = {{Rank, Trace-Norm and Max-Norm}},
  author    = {Srebro, Nathan and Shraibman, Adi},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2005},
  pages     = {545-560},
  doi       = {10.1007/11503415_37},
  url       = {https://mlanthology.org/colt/2005/srebro2005colt-rank/}
}