Open ghost opened 4 years ago
models.Article{
UID: "0x11c",
ArXivID: "1209.0001",
Title: "An Improved Bound for the Nystrom Method for Large Eigengap",
Abstract: "We develop an improved bound for the approximation error of the Nystr\\\"{o}m\nmethod under the assumption that there is a large eigengap in the spectrum of\nkernel matrix. This is based on the empirical observation that the eigengap has\na significant impact on the approximation error of the Nystr\\\"{o}m method. Our\napproach is based on the concentration inequality of integral operator and the\ntheory of matrix perturbation. Our analysis shows that when there is a large\neigengap, we can improve the approximation error of the Nystr\\\"{o}m method from\n$O(N/m^{1/4})$ to $O(N/m^{1/2})$ when measured in Frobenius norm, where $N$ is\nthe size of the kernel matrix, and $m$ is the number of sampled columns.",
SubmissionDate: 2012-08-30 00:00:00 UTC,
CrawledAt: 2020-06-06 15:05:44 UTC,
HTMLResponse: "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Transitional//EN\" \"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd\">\n<html xmlns=\"http://www.w3.org/1999/xhtml\" lang=\"en\">\n<head>\n<title>[1209.0001] An Improved Bound for the Nystrom Method for Large Eigengap</title>\n<link rel=\"shortcut icon\" href=\"/favicon.ico\" type=\"image/x-icon\" />\n<link rel=\"stylesheet\" type=\"text/css\" media=\"screen\" href=\"/css/arXiv.css?v=20191216\" />\n<link rel=\"stylesheet\" type=\"text/css\" media=\"screen\" href=\"/bibex/bibex.css?20181009\">\n<link rel=\"stylesheet\" type=\"text/css\" media=\"screen\" href=\"https://static.arxiv.org/static/browse/0.2.7/css/browse_search.css\" />\n<link rel=\"stylesheet\" href=\"https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css\"> \n<meta name=\"citation_title\" content=\"An Improved Bound for the Nystrom Method for Large Eigengap\" />\n<meta name=\"citation_author\" content=\"Mahdavi, Mehrdad\" />\n<meta name=\"citation_author\" content=\"Yang, Tianbao\" />\n<meta name=\"citation_author\" content=\"Jin, Rong\" />\n<meta name=\"citation_date\" content=\"2012/08/30\" />\n<meta name=\"citation_online_date\" content=\"2012/08/30\" />\n<meta name=\"citation_pdf_url\" content=\"http://arxiv.org/pdf/1209.0001\" />\n<meta name=\"citation_arxiv_id\" content=\"1209.0001\" />\n<script src=\"/js/mathjaxToggle.min.js\" type=\"text/javascript\"></script>\n\n\n</head>\n<body class=\"with-cu-identity\">\n\n<div id=\"cu-identity\">\n<div id=\"cu-logo\">\n<a href=\"https://www.cornell.edu/\"><img src=\"//static.arxiv.org/icons/cu/cornell-reduced-white-SMALL.svg\" alt=\"Cornell University\" width=\"200\" border=\"0\" /></a>\n</div>\n<div id=\"support-ack\">\n<a href=\"https://confluence.cornell.edu/x/ALlRF\">We gratefully acknowledge support from<br /> the Simons Foundation and member institutions.</a>\n</div>\n</div>\n<div id=\"header\">\n<h1><a href=\"/\">export.arXiv.org</a> > <a href=\"/list/cs/recent\">cs</a> > arXiv:1209.0001</h1>\n<div id=\"search\">\n<form id=\"search-arxiv\" method=\"post\" action=\"/search_classic\">\n\n<div class=\"wrapper-search-arxiv\">\n<input class=\"keyword-field\" type=\"text\" name=\"query\" placeholder=\"Search or Article ID\"/>\n\n<div class=\"filter-field\">\n <select name=\"searchtype\">\n<option value=\"all\" selected=\"selected\">All papers</option>\n<option value=\"ti\">Titles</option>\n<option value=\"au\">Authors</option>\n<option value=\"abs\">Abstracts</option>\n<option value=\"ft\">Full text</option>\n</select>\n</div>\n<input class=\"btn-search-arxiv\" value=\"\" type=\"submit\">\n<div class=\"links\">(<a href=\"/help\">Help</a> | <a href=\"/find\">Advanced search</a>)</div>\n</div>\n</form>\n</div>\n</div>\n<div id=\"content\">\n\n<!--\n<rdf:RDF xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\"\n xmlns:dc=\"http://purl.org/dc/elements/1.1/\"\n xmlns:trackback=\"http://madskills.com/public/xml/rss/module/trackback/\">\n <rdf:Description\n rdf:about=\"http://arxiv.org/abs/1209.0001\"\n dc:identifier=\"http://arxiv.org/abs/1209.0001\"\n dc:title=\"An Improved Bound for the Nystrom Method for Large Eigengap\"\n trackback:ping=\"http://arxiv.org/trackback/1209.0001\" />\n </rdf:RDF>\n-->\n\n<div id=\"abs\">\n<div class=\"extra-services\">\n\n<div class=\"full-text\">\n<span class=\"descriptor\">Full-text links:</span>\n<h2>Download:</h2>\n<ul>\n<li><a href=\"/pdf/1209.0001\" accesskey=\"f\">PDF</a></li>\n<li><a href=\"/ps/1209.0001\">PostScript</a></li>\n<li><a href=\"/format/1209.0001\">Other formats</a></li>\n</ul>\n<div class=\"abs-license\">(<a href=\"http://arxiv.org/licenses/nonexclusive-distrib/1.0/\" title=\"Rights to this article\">license</a>)</div>\n</div><!--end full-text-->\n\n<div class=\"browse\">\n<h3>Current browse context:</h3>\n<div class=\"current\">stat.ML</div>\n<div class=\"prevnext\"><span class=\"arrow\"><a href=\"http://arxiv.org/prevnext?site=export.arxiv.org&id=1209.0001&context=stat.ML&function=prev\" accesskey=\"p\" title=\"previous in stat.ML (accesskey p)\">< prev</a></span> | <span class=\"arrow\"><a href=\"http://arxiv.org/prevnext?site=export.arxiv.org&id=1209.0001&context=stat.ML&function=next\" accesskey=\"n\" title=\"next in stat.ML (accesskey n)\">next ></a></span>\n<br /></div>\n<div class=\"list\"><a href=\"/list/stat.ML/new\">new</a> | <a href=\"/list/stat.ML/recent\">recent</a> | <a href=\"/list/stat.ML/1209\">1209</a></div><h3>Change to browse by:</h3><div class=\"switch\">\n<a href=\"/abs/1209.0001?context=cs\">cs</a><br />\n<span class=\"subclass\"><a href=\"/abs/1209.0001?context=cs.LG\">cs.LG</a></span><br />\n<span class=\"subclass\"><a href=\"/abs/1209.0001?context=math.NA\">math.NA</a></span><br />\n<a href=\"/abs/1209.0001?context=stat\">stat</a>\n</div>\n\n</div>\n<div class=\"extra-ref-cite\">\n<h3>References & Citations</h3><ul><li><a href=\"http://adsabs.harvard.edu/cgi-bin/bib_query?arXiv:1209.0001\">NASA ADS</a></li>\n</ul>\n\n</div>\n<div class=\"bookmarks\">\n<div class=\"what-is-this\">\n<h3>Bookmark</h3> (<a href=\"/help/social_bookmarking\">what is this?</a>)\n</div>\n<a href=\"http://arxiv.org/ct?url=http%3A%2F%2Fwww.citeulike.org%2Fposturl%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001%26title%3DAn%2520Improved%2520Bound%2520for%2520the%2520Nystrom%2520Method%2520for%2520Large%2520Eigengap%26authors%3D&v=ccf50faa\" title=\"Bookmark on CiteULike\"><img src=\"//static.arxiv.org/icons/social/citeulike.png\" alt=\"CiteULike logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=http%3A%2F%2Fwww.bibsonomy.org%2FBibtexHandler%3FrequTask%3Dupload%26url%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001%26description%3DAn%2520Improved%2520Bound%2520for%2520the%2520Nystrom%2520Method%2520for%2520Large%2520Eigengap&v=87a6cdb5\" title=\"Bookmark on BibSonomy\"><img src=\"//static.arxiv.org/icons/social/bibsonomy.png\" alt=\"BibSonomy logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=https%3A%2F%2Fwww.mendeley.com%2Fimport%2F%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001&v=a42c630d\" title=\"Bookmark on Mendeley\"><img src=\"//static.arxiv.org/icons/social/mendeley.png\" alt=\"Mendeley logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=https%3A%2F%2Fdel.icio.us%2Fpost%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001%26description%3DAn%2520Improved%2520Bound%2520for%2520the%2520Nystrom%2520Method%2520for%2520Large%2520Eigengap&v=4babc94b\" title=\"Bookmark on del.icio.us\"><img src=\"//static.arxiv.org/icons/social/delicious.png\" alt=\"del.icio.us logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=https%3A%2F%2Fdigg.com%2Fsubmit%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001%26title%3DAn%2520Improved%2520Bound%2520for%2520the%2520Nystrom%2520Method%2520for%2520Large%2520Eigengap&v=0d190a36\" title=\"Bookmark on Digg\"><img src=\"//static.arxiv.org/icons/social/digg.png\" alt=\"Digg logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=https%3A%2F%2Freddit.com%2Fsubmit%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001%26title%3DAn%2520Improved%2520Bound%2520for%2520the%2520Nystrom%2520Method%2520for%2520Large%2520Eigengap&v=b53f4657\" title=\"Bookmark on Reddit\"><img src=\"//static.arxiv.org/icons/social/reddit.png\" alt=\"Reddit logo\" /></a>\n<a href=\"http://arxiv.org/ct?url=http%3A%2F%2Fsciencewise.info%2Fbookmarks%2Fadd%3Furl%3Dhttp%3A%2F%2Farxiv.org%2Fabs%2F1209.0001&v=627ddfcc\" title=\"Bookmark on ScienceWISE\"><img src=\"//static.arxiv.org/icons/social/sciencewise.png\" alt=\"ScienceWISE logo\" /></a>\n\n</div>\n</div><!--end extra-services-->\n\n<div class=\"leftcolumn\">\n<div class=\"subheader\">\n<h1>Computer Science > Machine Learning</h1>\n</div>\n<h1 class=\"title mathjax\"><span class=\"descriptor\">Title:</span>\nAn Improved Bound for the Nystrom Method for Large Eigengap</h1>\n<div class=\"authors\"><span class=\"descriptor\">Authors:</span>\n<a href=\"/find/cs/1/au:+Mahdavi_M/0/1/0/all/0/1\">Mehrdad Mahdavi</a>, \n<a href=\"/find/cs/1/au:+Yang_T/0/1/0/all/0/1\">Tianbao Yang</a>, \n<a href=\"/find/cs/1/au:+Jin_R/0/1/0/all/0/1\">Rong Jin</a></div>\n<div class=\"dateline\">(Submitted on 30 Aug 2012)</div>\n<blockquote class=\"abstract mathjax\">\n<span class=\"descriptor\">Abstract:</span> We develop an improved bound for the approximation error of the Nystr\\\"{o}m\nmethod under the assumption that there is a large eigengap in the spectrum of\nkernel matrix. This is based on the empirical observation that the eigengap has\na significant impact on the approximation error of the Nystr\\\"{o}m method. Our\napproach is based on the concentration inequality of integral operator and the\ntheory of matrix perturbation. Our analysis shows that when there is a large\neigengap, we can improve the approximation error of the Nystr\\\"{o}m method from\n$O(N/m^{1/4})$ to $O(N/m^{1/2})$ when measured in Frobenius norm, where $N$ is\nthe size of the kernel matrix, and $m$ is the number of sampled columns.\n</blockquote>\n<!--CONTEXT-->\n<div class=\"metatable\">\n<table summary=\"Additional metadata\">\n<tr>\n<td class=\"tablecell label\">Subjects:\n</td>\n<td class=\"tablecell subjects\"><span class=\"primary-subject\">Machine Learning (cs.LG)</span>; Numerical Analysis (math.NA); Machine Learning (stat.ML)</td>\n</tr>\n<tr>\n<td class=\"tablecell label\">\nCite as:\n</td>\n<td class=\"tablecell arxivid\"><a href=\"/abs/1209.0001\">arXiv:1209.0001</a> [cs.LG]</td>\n</tr>\n<tr>\n<td class=\"tablecell label\"> </td>\n<td class=\"tablecell arxividv\">(or <span class=\"arxivid\"><a href=\"/abs/1209.0001v1\">arXiv:1209.0001v1</a> [cs.LG]</span> for this version)</td>\n</tr>\n</table>\n</div>\n<div class=\"submission-history\">\n<h2>Submission history</h2>\nFrom: Mehrdad Mahdavi [<a href=\"https://arxiv.org/show-email/60c3ba82/1209.0001\">view email</a>]\n<br />\n<b>[v1]</b> Thu, 30 Aug 2012 20:40:06 GMT (19kb)<br />\n</div>\n<div class=\"endorsers\"><a href=\"http://arxiv.org/auth/show-endorsers/1209.0001\">Which authors of this paper are endorsers?</a> | <a id=\"mathjax_toggle\" href=\"javascript:setMathjaxCookie()\">Disable MathJax</a> (<a href=\"/help/mathjax/\">What is MathJax?</a>) </div><script type=\"text/javascript\" language=\"javascript\">mathjaxToggle();</script>\n<script src=\"/bibex/bibex.js?20181009\" type=\"text/javascript\" defer></script>\n</div><!--end leftcolumn-->\n</div><!--end abs-->\n<p>Link back to: <a href=\"http://arXiv.org/\">arXiv</a>, <a href=\"http://arxiv.org/form\">form interface</a>, <a href=\"/help/contact\">contact</a>.</p>\n</div>\n</div>\n <footer style=\"clear: both;\">\n <div class=\"columns is-desktop\" role=\"navigation\" aria-label=\"Secondary\" style=\"margin: -0.75em -0.75em 0.75em -0.75em\">\n <!-- Macro-Column 1 -->\n <div class=\"column\" style=\"padding: 0;\">\n <div class=\"columns\">\n <div class=\"column\">\n <ul style=\"list-style: none; line-height: 2;\">\n <li><a href=\"https://arxiv.org/about\">About arXiv</a></li>\n <li><a href=\"https://arxiv.org/about/people/leadership_team\">Leadership Team</a></li>\n </ul>\n </div>\n <div class=\"column\">\n <ul style=\"list-style: none; line-height: 2;\">\n <li>\n <svg xmlns=\"http://www.w3.org/2000/svg\" viewBox=\"0 0 512 512\" class=\"icon filter-white\" role=\"presentation\"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d=\"M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z\"/></svg>\n <a href=\"{{ url_for('contact') }}\"> Contact</a>\n </li>\n <li>\n <svg xmlns=\"http://www.w3.org/2000/svg\" viewBox=\"0 0 512 512\" class=\"icon filter-white\" role=\"presentation\"><title>arXiv Twitter</title><desc>arXiv Twitter</desc><path d=\"M459.37 151.716c.325 4.548.325 9.097.325 13.645 0 138.72-105.583 298.558-298.558 298.558-59.452 0-114.68-17.219-161.137-47.106 8.447.974 16.568 1.299 25.34 1.299 49.055 0 94.213-16.568 130.274-44.832-46.132-.975-84.792-31.188-98.112-72.772 6.498.974 12.995 1.624 19.818 1.624 9.421 0 18.843-1.3 27.614-3.573-48.081-9.747-84.143-51.98-84.143-102.985v-1.299c13.969 7.797 30.214 12.67 47.431 13.319-28.264-18.843-46.781-51.005-46.781-87.391 0-19.492 5.197-37.36 14.294-52.954 51.655 63.675 129.3 105.258 216.365 109.807-1.624-7.797-2.599-15.918-2.599-24.04 0-57.828 46.782-104.934 104.934-104.934 30.213 0 57.502 12.67 76.67 33.137 23.715-4.548 46.456-13.32 66.599-25.34-7.798 24.366-24.366 44.833-46.132 57.827 21.117-2.273 41.584-8.122 60.426-16.243-14.292 20.791-32.161 39.308-52.628 54.253z\"/></svg>\n <a href=\"{{ url_for('twitter') }}\"> <span class=\"is-hidden-mobile\">Follow us on</span> Twitter</a>\n </li>\n </ul>\n </div>\n </div>\n </div>\n <!-- End Macro-Column 1 -->\n <!-- Macro-Column 2 -->\n <div class=\"column\" style=\"padding: 0;\">\n <div class=\"columns\">\n <div class=\"column\">\n <ul style=\"list-style: none; line-height: 2;\">\n <li><a href=\"https://arxiv.org/help\">Help</a></li>\n <li><a href=\"https://arxiv.org/help/policies/privacy_policy\">Privacy Policy</a></li>\n </ul>\n </div>\n <div class=\"column\">\n <ul style=\"list-style: none; line-height: 2;\">\n <li><a href=\"https://blogs.cornell.edu/arxiv\">Blog</a></li>\n <li><a href=\"https://arxiv.org/help/subscribe\"> Subscribe</a></li>\n </ul>\n </div>\n </div>\n </div>\n <!-- End Macro-Column 2 -->\n </div>\n\n <div class=\"columns\" style=\"border-top: 1px solid #979797; margin: -0.75em;\">\n <div class=\"column\">\n <p class=\"help\" style=\"margin-bottom: 0;\">arXiv® is a registered trademark of Cornell University.</p>\n </div>\n <div class=\"column\">\n <p class=\"help\" style=\"margin-bottom: 0;\">If you have a disability and are having trouble accessing information on this website or need materials in an alternate format,\n contact <a href=\"mailto:web-accessibility@cornell.edu\">web-accessibility@cornell.edu</a> for assistance.</p>\n </div>\n </div>\n </footer>\n</body>\n</html>\n",
PDFURL: "https://export.arxiv.org/pdf/1209.0001",
OtherFormatURL: "https://export.arxiv.org/format/1209.0001",
MetaURL: "https://export.arxiv.org/abs/1209.0001?context=stat.ML",
Authors: []models.Author{
models.Author{
UID: "0x11d",
Name: "Mahdavi_M",
URL: "https://export.arxiv.org/find/cs/1/au:+Mahdavi_M/0/1/0/all/0/1",
DType: []string{
"Author",
},
},
models.Author{
UID: "0x11e",
Name: "Yang_T",
URL: "https://export.arxiv.org/find/cs/1/au:+Yang_T/0/1/0/all/0/1",
DType: []string{
"Author",
},
},
models.Author{
UID: "0x11f",
Name: "Jin_R",
URL: "https://export.arxiv.org/find/cs/1/au:+Jin_R/0/1/0/all/0/1",
DType: []string{
"Author",
},
},
},
CitedPapers: []models.Article{},
DType: []string{
"Article",
},
}
{"level":"fatal","ts":1591455944.9509234,"caller":"databases/graphdb.go:73","msg":"Transaction has been aborted. Please retry","stacktrace":"pandor/databases.AddArticle\n\t/home/ubuntu/lucmichalski/pandor/databases/graphdb.go:73\npandor/scrappers.LaunchArXiv.func2\n\t/home/ubuntu/lucmichalski/pandor/scrappers/arxiv.go:187\ngithub.com/gocolly/colly/v2.(*Collector).handleOnHTML.func1\n\t/home/ubuntu/go/pkg/mod/github.com/gocolly/colly/v2@v2.0.1/colly.go:990\ngithub.com/PuerkitoBio/goquery.(*Selection).Each\n\t/home/ubuntu/go/pkg/mod/github.com/!puerkito!bio/goquery@v1.5.1/iteration.go:10\ngithub.com/gocolly/colly/v2.(*Collector).handleOnHTML\n\t/home/ubuntu/go/pkg/mod/github.com/gocolly/colly/v2@v2.0.1/colly.go:980\ngithub.com/gocolly/colly/v2.(*Collector).fetch\n\t/home/ubuntu/go/pkg/mod/github.com/gocolly/colly/v2@v2.0.1/colly.go:639"}
a more detailed debug information on the issue.
Hi,
Hope you are all well !
I tried your script and after a couple of links crawled, I have the following error:
What is happening ? Is it possible to fix it ?
Cheers, X