{"entities":{"Q1072298":{"pageid":1083050,"ns":120,"title":"Item:Q1072298","lastrevid":66227088,"modified":"2026-04-12T08:23:49Z","type":"item","id":"Q1072298","labels":{"en":{"language":"en","value":"Algorithms and complexity for least median of squares regression"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3942763"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$77F34A1C-500E-4B36-A518-B6EE38507F29","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63ab3826380e13e2613e8a8ecadc933cf595e3b1","datavalue":{"value":{"text":"Algorithms and complexity for least median of squares regression","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1072298$0E37159D-7C07-4D54-9E81-CFD63D95E1FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab3b071fe8c561e169fa30a93c0dfe4365ac1846","datavalue":{"value":"0587.62078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$34D09A8F-97B5-46A7-AA3E-0FF441544D68","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fa917a329e783292df13e82002a3ad55fcf6dc6","datavalue":{"value":"10.1016/0166-218X(86)90009-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$D762E2E3-F5D6-4CBE-9D52-A487EDE193CD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$55142A69-7D17-44DF-86A7-5516BB4242DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1072298$A5CDE1D1-1A26-4075-875A-3319929DE5A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6cd1626aef4bf04857186cf0e6ad33df32d3b344","datavalue":{"value":"Given n points \\(\\{(x_ i,y_ i)\\}\\) in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function \\(f(\\alpha,\\beta)=median(| y_ i-(\\alpha +\\beta x_ i)|);\\) it is piecewise linear and can have a quadratic number of local minima.    Several algorithms that locate a minimizer of f are presented. The best of these has time complexity \\(O(n^ 3)\\) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of \\(O(n^ 3\\log (n))\\), but we provide a probabilistic speed-up of this algorithm which appears to have expected time complexity of O((n log(n))\\({}^ 2)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$A3F2E656-0D34-4E8C-BD00-C63EAFFF41F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a4dbf529fe501a8125be9da861e7c4a1450806a","datavalue":{"value":"62F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$17A67851-A434-461E-AD70-1D8183A0BAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9d53b6d887f8d02f744e09bef54fb1930d2da928","datavalue":{"value":"65C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$5A29DA15-F504-4C85-A721-29FD270854F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$CFC67A8B-661C-4955-9AAE-C040607FD2BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"586ab8f81afd2dc238b42fa3a7f2641cea86e995","datavalue":{"value":"3942763","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$A9CFCA26-EDD7-4337-85A8-1D5F566D3163","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"107ccf9dc7ff80a1bf8e2292de606432528635c2","datavalue":{"value":"breakdown point","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$6E85DBED-A75C-4269-BC42-5763DCAFF833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f762bc1a389b4540cd169b666dbaf1a8451c7cb2","datavalue":{"value":"robustness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$5E5A15C7-E45C-46B7-970A-103286C78088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91ccfd60d0b95e96556cbc1ddd94c8ec4bb9ef2e","datavalue":{"value":"least median of squares regression line","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$551731C3-AB89-41C6-8BA8-F456DD999450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0dfeaa15526caecb2a6845352ecfc54328a30cd","datavalue":{"value":"piecewise linear","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$9D162FF9-A749-4BC4-AA86-BFE65D6B2F51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11a6262982fbf481b0d56c3df38de448b97c1453","datavalue":{"value":"quadratic number of local minima","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$86311D20-8621-46AF-92E2-8DC30E1D8ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$0F1BAD3B-BA3C-44DC-9640-16ADC758809D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072298$F10AD350-924B-4B57-9A4C-B731B2A4C9EA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"78e9f7badb2d3e5d06a7bd59d576de6739bcee7e","datavalue":{"value":{"entity-type":"item","numeric-id":341604,"id":"Q341604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$A9F0896B-8AEB-408E-9113-3BC001FA6A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f30d3eeaa962fa9c515f69147b2dd92e48340d2d","datavalue":{"value":{"entity-type":"item","numeric-id":603846,"id":"Q603846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$8DA77E2F-B839-41D4-82E1-F8A1CCEEAB45","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$F0FF8486-F47B-41FE-8F06-E5604E81758C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a735b34d19b5ce4cb570242a6d4af8dc6baf3869","datavalue":{"value":{"entity-type":"item","numeric-id":3673862,"id":"Q3673862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$8F635749-8242-4146-B41F-62AAD7F6CC01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f627ffcf38e715df1079ffaf2441dcfdb46b4542","datavalue":{"value":{"entity-type":"item","numeric-id":5637764,"id":"Q5637764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$1B4DA2F9-050C-47C5-AEB8-480A4FFFCF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3bb23c86421ecad28c04c6670083c4931c6a641","datavalue":{"value":{"entity-type":"item","numeric-id":5612956,"id":"Q5612956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$1CDCBD49-1873-4DE4-90A4-37E43B366238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305ecfb687b7a10a65d2c6d38c1424b17fe1e690","datavalue":{"value":{"entity-type":"item","numeric-id":3343267,"id":"Q3343267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$EDA26859-7296-45C9-AAE5-9A030B08C289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8651498b4d4a3729f82905edb3c58f0c89f353","datavalue":{"value":{"entity-type":"item","numeric-id":3339116,"id":"Q3339116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072298$ED1F1479-3996-461B-BFB5-DEC62D5C0EA9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"469f2ee48c178197b1a068114360a0ad29694ebe","datavalue":{"value":"https://doi.org/10.1016/0166-218x(86)90009-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1072298$70548B0D-5F22-4B24-8B18-BA2A1C651693","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"835687d3d2861f2e04254dd74978efc649bb6381","datavalue":{"value":"W2060909287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072298$9D332A01-9766-44BF-86CA-2BD4584E3089","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3acbe3a0f9bf0dafcdd359432ab419c7b3349ba0","datavalue":{"value":{"entity-type":"item","numeric-id":3771429,"id":"Q3771429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43c0e466fac48e49e37be064bc28b95d9f9bbb26","datavalue":{"value":{"amount":"+0.9014315605163574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1072298$FA442E5B-BF98-4588-B563-9669BFEC92A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9db8d9a3a275e39b84890d0e499459a4de31f7f","datavalue":{"value":{"entity-type":"item","numeric-id":3481105,"id":"Q3481105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cde0cedea4121640fb7571c6af670700cc18221","datavalue":{"value":{"amount":"+0.8980520963668823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1072298$0F800E1A-B390-4211-86FF-E67958C0111D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94a6f98ee3e9a1d42546626e82ed64ef74c44236","datavalue":{"value":{"entity-type":"item","numeric-id":854711,"id":"Q854711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab9291aa81dec2b303271bb83b21ede050645f56","datavalue":{"value":{"amount":"+0.8634757995605469","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1072298$B7108061-2E13-40EA-92FB-98252703519E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18133b7a20f4720635b4810cd2e12b28fda88986","datavalue":{"value":{"entity-type":"item","numeric-id":5361680,"id":"Q5361680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa22d9fbfb5f378a25f0830f92a020c567a97621","datavalue":{"value":{"amount":"+0.8539326786994934","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1072298$8C3BEF9B-D28B-418B-8FF0-DFB7A8BD27B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b216abe4690c517dc447c7bbd008edebded2eee","datavalue":{"value":{"entity-type":"item","numeric-id":4763428,"id":"Q4763428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78c1a1b204101f646ad28f7e4d93ac41371571a6","datavalue":{"value":{"amount":"+0.8306117057800293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1072298$1D6113C2-E353-4070-ACDB-38FC5C274273","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms and complexity for least median of squares regression","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_and_complexity_for_least_median_of_squares_regression"}}}}}