links for 2011-​​04-​​02

links for 2010-​​08-​​12

  • “In this work we intro­duce a new lin­ear time com­pres­sion algo­rithm, called “Re-​​pair for Trees”, which com­presses ranked ordered trees using lin­ear straight-​​line context-​​free tree gram­mars. Such gram­mars gen­er­al­ize straight-​​line context-​​free string gram­mars and allow basic tree oper­a­tions, like tra­ver­sal along edges, to be exe­cuted with­out prior decom­pres­sion. Our algo­rithm can be con­sid­ered as a gen­er­al­iza­tion of the “Re-​​pair” algo­rithm devel­oped by N. Jes­per Lars­son and Alis­tair Mof­fat in 2000. The lat­ter algo­rithm is a dictionary-​​based com­pres­sion algo­rithm for strings. We also intro­duce a suc­cinct cod­ing which is spe­cial­ized in fur­ther com­press­ing the gram­mars gen­er­ated by our algo­rithm. This is accom­plished with­out loos­ing the abil­ity do directly exe­cute queries on this com­pressed rep­re­sen­ta­tion of the input tree.…”
  • “Until I started using Spec­i­fi­ca­tion Work­shops as the name for a col­lab­o­ra­tive meet­ing about accep­tance tests, it was very hard to con­vince busi­ness users to par­tic­i­pate. But a sim­ple change in nam­ing made the prob­lem go away.”
  • “Weather data didn’t come to be because of an Open Gov­ern­ment Direc­tive. It wasn’t cre­ated because of a White House man­date. Gov­ern­ment did not release the data and then enter­pris­ing peo­ple built com­pa­nies on top of it. It’s more accu­rate to make the argu­ment that we have a national weather ser­vice because of one man’s deep desire to keep his job and to get pro­moted to colonel in the Army. It could be a vast net­work of lob­by­ists to help that man get pro­moted, or the vast net­work of lob­by­ists from ship­ping com­pa­nies try­ing to get access to data already being cre­ated. Or it could be that it was just pretty obvi­ous that access to weather data would save lives.”
  • “While com­pany fil­ings and reg­u­la­tions may not be the most glam­orous parts of your startup, they’re absolutely crit­i­cal to the suc­cess of your busi­ness and safety of your per­sonal sav­ings. Here’s a quick run­down of the laws and reg­u­la­tions you need to con­sider when cre­at­ing a startup. Of course, depend­ing on your type of busi­ness, hir­ing a tax accoun­tant or good attor­ney with spe­cific expe­ri­ence in your indus­try can go a long way to help­ing you steer clear of trouble.”
  • “We study, using sim­u­lated exper­i­ments inspired by thin film mag­netic domain pat­terns, the fea­si­bil­ity of phase retrieval in X-​​ray dif­frac­tive imag­ing in the pres­ence of intrin­sic charge scat­ter­ing given only photon-​​shot-​​noise lim­ited dif­frac­tion data. We detail a recon­struc­tion algo­rithm to recover the sample’s mag­ne­ti­za­tion dis­tri­b­u­tion under such con­di­tions, and com­pare its per­for­mance with that of Fourier trans­form holog­ra­phy. Con­cern­ing the design of future exper­i­ments, we also chart out the recon­struc­tion lim­its of dif­frac­tive imag­ing when pho­ton– shot-​​noise and the inten­sity of charge scat­ter­ing noise are inde­pen­dently var­ied. This work is directly rel­e­vant to the time-​​resolved imag­ing of mag­netic dynam­ics using coher­ent and ultra­fast radi­a­tion from X-​​ray free elec­tron lasers and also to broader classes of dif­frac­tive imag­ing exper­i­ments which suf­fer noisy data, miss­ing data or both.”
  • “We have shown that there exists a large ensem­ble of min­i­mal Boolean net­works that show reli­able and robust dynam­ics. The net­works are min­i­mal in the respect that the num­ber of con­nec­tions of a node is not larger than nec­es­sary for obtain­ing a desired reli­able tra­jec­tory. A reli­able tra­jec­tory is an attrac­tor of the dynam­ics of the net­work that does not change when the update sched­ule is changed or ran­dom­ized. This means that under par­al­lel update, at each time step only one node changes its state. The reli­able tra­jec­to­ries were cho­sen at ran­dom, given a fixed aver­age num­ber of flips per node. High robust­ness was achieved by using an evo­lu­tion­ary algo­rithm that mod­i­fies the update func­tions and that accepts only those changes that do not decrease robustness.…”
  • “Our 2.546-approximation is quite sim­ple. The per­for­mance guar­an­tee is based on a sim­ple area argu­ment. This gives rise to the fol­low­ing ques­tion: what is the small­est square that suf­fices for pack­ing any set of cir­cles of total area 1? We believe the worst-​​case may very well be shown in Fig­ure 13, which yields a lower bound of 1.471299… We believe there are rel­a­tively easy ways to improve the upper bound.”
  • “In this paper we present a tech­nique for fusion of opti­cal and ther­mal face images based on image pixel fusion approach. Out of sev­eral fac­tors, which affect face recog­ni­tion per­for­mance in case of visual images, illu­mi­na­tion changes are a sig­nif­i­cant fac­tor that needs to be addressed. Ther­mal images are bet­ter in han­dling illu­mi­na­tion con­di­tions but not very con­sis­tent in cap­tur­ing tex­ture details of the faces. Other fac­tors like sun­glasses, beard, mous­tache etc also play active role in adding com­pli­ca­cies to the recog­ni­tion process. Fusion of ther­mal and visual images is a solu­tion to over­come the draw­backs present in the indi­vid­ual ther­mal and visual face images.…”
  • “OpenCV (Open Source Com­puter Vision) is a library of pro­gram­ming func­tions for real time com­puter vision.

    OpenCV is released under a BSD license, it is free for both aca­d­e­mic and com­mer­cial use.
    The library has >500 opti­mized algo­rithms (see fig­ure below). It is used around the world, has >2M down­loads and >40K peo­ple in the user group. Uses range from inter­ac­tive art, to mine inspec­tion, stitch­ing maps on the web on through advanced robotics.”

  • “We study the dynam­ics of the Nam­ing Game [Baronchelli et al., (2006) J. Stat. Mech.: The­ory Exp. P06014] in empir­i­cal social net­works. This styl­ized agent-​​based model cap­tures essen­tial fea­tures of agree­ment dynam­ics in a net­work of autonomous agents, cor­re­spond­ing to the devel­op­ment of shared clas­si­fi­ca­tion schemes in a net­work of arti­fi­cial agents or opin­ion spread­ing and social dynam­ics in social net­works. Our study focuses on the impact that com­mu­ni­ties in the under­ly­ing social graphs have on the out­come of the agree­ment process. We find that net­works with strong com­mu­nity struc­ture hin­der the sys­tem from reach­ing global agree­ment; the evo­lu­tion of the Nam­ing Game in these net­works main­tains clus­ters of coex­ist­ing opin­ions indef­i­nitely. Fur­ther, we inves­ti­gate agent-​​based net­work strate­gies to facil­i­tate con­ver­gence to global consensus.”
  • “Neu­ronal activ­ity arises from an inter­ac­tion between ongo­ing fir­ing gen­er­ated spon­ta­neously by neural cir­cuits and responses dri­ven by exter­nal stim­uli. Using mean-​​field analy­sis, we ask how a neural net­work that intrin­si­cally gen­er­ates chaotic pat­terns of activ­ity can remain sen­si­tive to extrin­sic input. We find that inputs not only drive net­work responses, they also actively sup­press ongo­ing activ­ity, ulti­mately lead­ing to a phase tran­si­tion in which chaos is com­pletely elim­i­nated. The crit­i­cal input inten­sity at the phase tran­si­tion is a non-​​monotonic func­tion of stim­u­lus fre­quency, reveal­ing a “res­o­nant” fre­quency at which the input is most effec­tive at sup­press­ing chaos even though the power spec­trum of the spon­ta­neous activ­ity peaks at zero and falls expo­nen­tially. A pre­dic­tion of our analy­sis is that the vari­ance of neural responses should be most strongly sup­pressed at fre­quen­cies match­ing the range over which many sen­sory sys­tems operate.”
  • “Devel­op­ing large-​​scale dis­trib­uted appli­ca­tions can be a daunt­ing task. object-​​based envi­ron­ments have attempted to alle­vi­ate prob­lems by pro­vid­ing dis­trib­uted objects that look like local objects. We advo­cate that this approach has actu­ally only made mat­ters worse, as the devel­oper needs to be aware of many intri­cate inter­nal details in order to ade­quately han­dle par­tial fail­ures. The result is an increase of appli­ca­tion com­plex­ity. We present an alter­na­tive in which dis­tri­b­u­tion trans­parency is less­ened in favor of clearer seman­tics. In par­tic­u­lar, we argue that a devel­oper should always be offered the unam­bigu­ous seman­tics of local objects, and that dis­tri­b­u­tion comes from copy­ing those objects to where they are needed. We claim that it is often suf­fi­cient to pro­vide only small, immutable objects, along with facil­i­ties to group objects into clusters.”
  • “The task of image restra­tion is to find the spa­tial cor­re­spon­dence of two or more given images. In this paper we assume that the cor­re­spon­dence is given either by an Euclid­ean, or by an affine volume-​​preserving trans­for­ma­tion. Since the reg­is­tra­tion prob­lem can be seen as an opti­miza­tion prob­lem on a finite dimen­sional Lie group, we use a recently devel­oped frame­work of approximate-​​Newton meth­ods on man­i­folds, which leads to locally qua­drat­i­cally con­ver­gent algo­rithms. To reduce numer­i­cal costs, we present two strate­gies: One makes use of the quasi Monte Carlo Method and the other ends up with an algo­rithm act­ing on spline func­tion spaces. An exten­sion for multi-​​modal image reg­is­tra­tion is given as well.”
  • “l1-​​minimization refers to find­ing the min­i­mum l1-​​norm solu­tion to an under­de­ter­mined lin­ear sys­tem b=Ax. It has recently received much atten­tion, mainly moti­vated by the new com­pres­sive sens­ing the­ory that shows that under quite gen­eral con­di­tions the min­i­mum l1-​​norm solu­tion is also the spars­est solu­tion to the sys­tem of lin­ear equa­tions. Although the under­ly­ing prob­lem is a lin­ear pro­gram, con­ven­tional algo­rithms such as interior-​​point meth­ods suf­fer from poor scal­a­bil­ity for large-​​scale real world prob­lems. A num­ber of accel­er­ated algo­rithms have been recently pro­posed that take advan­tage of the spe­cial struc­ture of the l1-​​minimization prob­lem. In this paper, we pro­vide a com­pre­hen­sive review of five rep­re­sen­ta­tive approaches, namely, Gra­di­ent Pro­jec­tion, Homo­topy, Iter­a­tive Shrinkage-​​Thresholding, Prox­i­mal Gra­di­ent, and Aug­mented Lagrange Multiplier. …”
  • “Sparse data mod­els, where data is assumed to be well rep­re­sented as a lin­ear com­bi­na­tion of a few ele­ments from a dic­tio­nary, have gained con­sid­er­able atten­tion in recent years, and their use has led to state-​​of-​​the-​​art results in many sig­nal and image pro­cess­ing tasks. It is now well under­stood that the choice of the spar­sity reg­u­lar­iza­tion term is crit­i­cal in the suc­cess of such mod­els. Based on a code­length min­i­miza­tion inter­pre­ta­tion of sparse cod­ing, and using tools from uni­ver­sal cod­ing the­ory, we pro­pose a frame­work for design­ing spar­sity reg­u­lar­iza­tion terms which have the­o­ret­i­cal and prac­ti­cal advan­tages when com­pared to the more stan­dard l0 or l1 ones. The pre­sen­ta­tion of the frame­work and the­o­ret­i­cal foun­da­tions is com­ple­mented with exam­ples that show its prac­ti­cal advan­tages in image denois­ing, zoom­ing and classification.”
  • “In the present arti­cle we empha­size the impor­tance of mod­el­ing time in the con­text of agent-​​based mod­els. To this end, we present a (selec­tive) sur­vey of the Cel­lu­lar Automata-​​literature on updat­ing and draw par­al­lels to the issue of agent acti­va­tion in agent-​​based mod­els. By means of two sim­ple mod­els, Schelling’s seg­re­ga­tion model and Epstein’s demo­graphic prisoner’s dilemma we inves­ti­gate the influ­ence of choos­ing dif­fer­ent regimes of agent acti­va­tion. Our exper­i­ments indi­cate that tim­ing is not a crit­i­cal issue for very sim­ple mod­els but bears huge influ­ence on model behav­ior and results as soon as the degree of com­plex­ity increases only so slightly. After a brief review of the way com­monly used ABM sim­u­la­tion envi­ron­ments han­dle the issue of tim­ing, we draw some ten­ta­tive con­clu­sions about the impor­tance of tim­ing and the need for more research towards that direc­tion, sim­i­lar to the con­certed effort on updat­ing in cel­lu­lar automata.”
  • “Tran­sient alge­bra is a multi-​​valued alge­bra for haz­ard detec­tion in gate cir­cuits. Sequences of alter­nat­ing 0’s and 1’s, called tran­sients, rep­re­sent sig­nal val­ues, and gates are mod­eled by exten­sions of boolean func­tions to tran­sients. For­mu­las for com­put­ing the out­put tran­sient of a gate from the input tran­sients are known for NOT, AND, OR} and XOR gates and their com­ple­ments, but, in gen­eral, even the prob­lem of decid­ing whether the length of the out­put tran­sient exceeds a given bound is NP-​​complete. We pro­pose a method of eval­u­at­ing exten­sions of gen­eral boolean func­tions. We intro­duce and study a class of func­tions with the fol­low­ing prop­erty: Instead of eval­u­at­ing an exten­sion of a boolean func­tion on a given set of tran­sients, it is pos­si­ble to get the same value by using tran­sients derived from the given ones, but hav­ing length at most 3. We prove that all func­tions of three vari­ables, as well as cer­tain other func­tions, have this prop­erty, and can be effi­ciently evaluated.”
  • “We define a two-​​step learner for RFSAs based on an obser­va­tion table by using an algo­rithm for min­i­mal DFAs to build a table for the rever­sal of the lan­guage in ques­tion and show­ing that we can derive the min­i­mal RFSA from it after some sim­ple mod­i­fi­ca­tions. We com­pare the algo­rithm to two other table-​​based ones of which one (by Bol­lig et al. 2009) infers a RFSA directly, and the other is another two-​​step learner pro­posed by the author. We focus on the cri­te­rion of query complexity.”
  • “…The model is based on the emer­gent prop­er­ties of generic genetic net­works, it does not refer to spe­cific con­trol cir­cuits and it can there­fore hold for a wide class of lin­eages. The model points to a pecu­liar role of cel­lu­lar noise in dif­fer­en­ti­a­tion, which has never been hypoth­e­sized so far, and leads to non triv­ial pre­dic­tions which could be sub­ject to exper­i­men­tal testing.”
  • “This paper presents a novel type-​​2 Fuzzy logic Sys­tem to define the Shape of a facial com­po­nent with the crisp out­put. This work is the part of our main research effort to design a sys­tem (called FASY) which offers a novel face con­struc­tion approach based on the tex­tual descrip­tion and also extracts and ana­lyzes the facial com­po­nents from a face image by an effi­cient tech­nique. The Fuzzy model, designed in this paper, takes crisp value of width and height of a facial com­po­nent and pro­duces the crisp value of Shape for dif­fer­ent facial com­po­nents. This method is designed using Mat­lab 6.5 and Visual Basic 6.0 and tested with the facial com­po­nents extracted from 200 male and female face images of dif­fer­ent ages from dif­fer­ent face databases.”
  • “We con­sider a gen­er­al­iza­tion of the Gabriel graph, the wit­ness Gabriel graph. Given a set of ver­tices P and a set of wit­nesses W in the plane, there is an edge ab between two points of P in the wit­ness Gabriel graph GG-(P,W) if and only if the closed disk with diam­e­ter ab does not con­tain any wit­ness point (besides pos­si­bly a and/​or b). We study sev­eral prop­er­ties of the wit­ness Gabriel graph, both as a prox­im­ity graph and as a new tool in graph drawing.”
  • “We use com­puter sim­u­la­tion to study crystal-​​forming model pro­teins equipped with inter­ac­tions that are both ori­en­ta­tion­ally spe­cific and non­spe­cific. Dis­tinct dynam­i­cal path­ways of crys­tal for­ma­tion can be selected by tun­ing the strengths of these inter­ac­tions. When the non­spe­cific inter­ac­tion is strong, liq­uid­like clus­ter­ing can pre­cede crys­tal­liza­tion; when it is weak, growth can pro­ceed via ordered nuclei. Crys­tal yields are in cer­tain para­me­ter regimes enhanced by the non­spe­cific inter­ac­tion, even though it pro­motes asso­ci­a­tion with­out local crys­talline order. Our results sug­gest that equip­ping nanoscale com­po­nents with weak non­spe­cific inter­ac­tions (such as deple­tion attrac­tions) can alter both their dynam­i­cal path­way of assem­bly and opti­mize the yield of the result­ing material.”
  • “Many com­plex sys­tems present an intrin­sic bipar­tite nature and are often described and mod­eled in terms of net­works [1–5]. Exam­ples include movies and actors [1, 2, 4], authors and sci­en­tific papers [6–9], email accounts and emails [10], plants and ani­mals that pol­li­nate them [11, 12]. Bipar­tite net­works are often very het­ero­ge­neous in the num­ber of rela­tion­ships that the ele­ments of one set estab­lish with the ele­ments of the other set. … Here we intro­duce an unsu­per­vised method to sta­tis­ti­cally val­i­date each link of the pro­jected net­work against a null hypoth­e­sis tak­ing into account the het­ero­gene­ity of the sys­tem. We apply our method to three dif­fer­ent sys­tems…. In all these sys­tems, both dif­fer­ent in size and level of het­ero­gene­ity, we find that our method is able to detect net­work struc­tures which are infor­ma­tive about the system…”
  • “Work out which bits of the sys­tem you know least about. Cre­ate the sce­nar­ios and have con­ver­sa­tions around those bits of the sys­tem. You don’t have to grow the sys­tem from the begin­ning – you can pick any point you like! Which bits of the sys­tem make you most uncom­fort­able? Which bits make your stake­hold­ers most uncomfortable?”
  • “So where does this gulf of expe­ri­ences come from, why is cucum­ber loved by some and hated by oth­ers. At the risk of over-​​generalisation and mis­char­ac­ter­i­sa­tion I recently came up with a the­ory: the cucum­ber detrac­tors are not using cuke the way it was intended.”

links for 2010-​​08-​​11

  • “We tried a vari­ant of this pro­gram start­ing in 2002 with a more solid econ­omy and we are still try­ing to recover from how that movie ended. Ein­stein defined insan­ity as doing the same thing over and over again and expect­ing dif­fer­ent results. And since the finan­cial sec­tor prof­ited so hand­somely from this exer­cise the last time around, they have every rea­son to encour­age this insanity.”
  • “In this work we inves­ti­gate a novel approach to han­dle the chal­lenges of face recog­ni­tion, which includes rota­tion, scale, occlu­sion, illu­mi­na­tion etc. Here, we have used ther­mal face images as those are capa­ble to min­i­mize the affect of illu­mi­na­tion changes and occlu­sion due to mous­tache, beards, adorn­ments etc. The pro­posed approach reg­is­ters the train­ing and test­ing ther­mal face images in polar coor­di­nate, which is capa­ble to han­dle com­pli­ca­cies intro­duced by scal­ing and rota­tion. Line fea­tures are extracted from ther­mal polar images and fea­ture vec­tors are con­structed using these line. Fea­ture vec­tors thus obtained passes through prin­ci­pal com­po­nent analy­sis (PCA) for the dimen­sion­al­ity reduc­tion of fea­ture vectors.…”
  • “In 1961 Her­bert Simon and Albert Ando pub­lished the the­ory behind the long-​​term behav­ior of a dynam­i­cal sys­tem that can be described by a nearly com­pletely decom­pos­able matrix. Over the past fifty years this the­ory has been used in a vari­ety of con­texts, includ­ing queue­ing the­ory, com­puter per­for­mance, and ecol­ogy. In all these appli­ca­tions, the struc­ture of the sys­tem is known and the point of inter­est is the var­i­ous states the sys­tem passes through on its way to some long-​​term equi­lib­rium. This paper looks at this prob­lem from the other direc­tion. That is, we develop a tech­nique for using the evo­lu­tion of the sys­tem to tell us about its ini­tial struc­ture, and we use this tech­nique to develop a new algo­rithm for data clustering.”
  • “Smoothie Charts is a really small chartling library designed for live stream­ing data. I built it to reduce the headaches I was get­ting from watch­ing charts jerk­ily updat­ing every sec­ond. What you’re look­ing up now is pretty much all it does. If you like that, then read on.”

links for 2010-​​08-​​10

links for 2010-​​08-​​02